冒泡排序
冒泡排序是一种简单的排序算法,其基本思想是重复地交换相邻两个元素,将较大的元素向右“冒泡”,较小的元素向左“沉淀”,从而将序列中的最大元素逐渐移到最后面。
#include <stdio.h>
void bub(int arr[],int n){ //首先定义空函数,第一个int参数接受列表,第二个为元素个数
int i,j,temp;
for(i=0;i<n-1;i++){ //这是进行几轮比较。这里是6轮。0,1,2,3,4,5 ,这里有-1可以减少不必要的比较轮次,到最后自己就排好了,因为不是几个数就比较就次,最后一个数会自己还原。
for(j=0;j<n-i-1;j++){ //下标从0开始而不1所以需要n-1。你如果不-1,后面j++,arr[j+1]会超出范围。-i是因为之后不需要再与最大数做比较了
if(arr[j]>arr[j+1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main(){
int arr[] = {64,34,97,12,22,11,90};
int n = sizeof(arr) / sizeof(arr[0]);
bub(arr,n);
printf("sort:\t");
for(int i = 0; i < n; i++) {
printf("%d\t",arr[i]);
}
return 0;
}
sort: 11 12 22 34 64 90 97
相较于其他排序算法,冒泡排序的优势在于它的实现简单、容易理解和编写,适用于少量数据的排序。此外,冒泡排序在交换相邻元素的过程中,可以记录是否发生了交换,如果没有发生交换则说明序列已经有序,可以提前结束排序,这样可以减少排序的时间复杂度。但是,对于大量数据排序,冒泡排序的时间复杂度为O(n^2),效率较低,因此不适用于大规模数据的排序。
优化冒泡
#include <stdio.h>
#include <stdbool.h> #有bool的时候最好加上
void bubble_sort(int arr[], int n) {
bool is_sorted = false;
int i, j, temp;
for (i = 0; i < n - 1; i++) {
is_sorted = true;
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) { //如果在这个for循环里,此if一次都未执行。那么is_sorted就不会变为false,也证明已经不需要换位置了。直接跳出当前循环,执行if语句,然后跳出大循环
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
is_sorted = false;
}
}
if (is_sorted) {
break;
}
}
}
int main() {
int arr[] = { 4, 2, 6, 1, 9, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int i;
bubble_sort(arr, n);
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
选择排序
选择排序是一种简单直观的排序算法,它的工作原理如下:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
#include <stdio.h>
void selectsort(int arr[],int n){
int min,i,j,temp;
for(i=0; i < n- 1; i++){
min=i; //取得最小的下标
for (j= i+1 ;j < n;j++) //每次都要比较到最后一个元素所以j<n
if(arr[j]<arr[min]){ //如果最小的下标的值不是最小值,将最小值的小标赋予min
min=j;
}
temp=arr[i]; //将这个最小下标的值存起来
arr[i]=arr[min]; //最小值赋予最小下标
arr[min]=temp; //将最小下标的值赋予min。也就是之前j的位置
}
}
int main(){
int a[] = {1,5,23,45,23,92,12};
int n = sizeof(a)/sizeof(a[0]);
selectsort(a,n);
for (int i = 0;i<n;i++) {
printf("%d\t", a[i]);
}
return 0;
}
快速排序
待排序的序列中,随机选一个数字作为pivot中心轴
所有小于中心轴放左,大于则放右边
左边比pivot中心轴小,而右边全比pivot大
然后对左子序列和右子序列重复以上的操作
/*
快速排序算法
思想: 递归思想
什么是递归?
自我调用(循环)的函数
有参数向着递归边界靠,直到达到递归边界
*/
/*
#include <stdio.h>
int f(int n){
if(n==0||n==1){
return 1;
} else{
return n*f(n-1);
}
}
int main(){
int n=5;
printf("%d ",f(n));
return 0;
}
*/
#include <stdio.h>
int FaindPos(int* a, int left, int right) {
int val = a[left];
while (left < right) {
while (left < right && a[right] >= val) {
right--;
}
a[left] = a[right];
while (left < right && a[left] <= val) {
left++;
}
a[right] = a[left];
}
a[left] = val;
return left;
}
void QuickSort(int* a, int left, int right) {
if (left >= right) {
return;
} else {
int val = a[left];
int pos = FaindPos(a, left, right);
a[pos] = val;
QuickSort(a, left, pos - 1);
QuickSort(a, pos + 1, right);
}
}
int main() {
int a[] = {6, 5, 7, 8, 3, 4, 2, 1};
QuickSort(a, 0, 7);
for (int i = 0; i < 8; i++) {
printf("%d ", a[i]);
}
return 0;
}
标签:arr,right,return,int,C语言,快排,冒泡,排序,left
From: https://www.cnblogs.com/supermao12/p/17142120.html