锐客网

  1. 首页 > it技术 > >

C语言——八大排序

一、冒泡排序
时间复杂度：平均情况：O(n^2) 最好情况：O(n)
空间复杂度：O(1)
稳定性：稳定
主要思路：
1.比较相邻的元素。如果第一个比第二个大，就交换它们两个。
2.对每一个相邻元素做同样的工作，从开始第一对到结尾的每一对。在这一 点，最后的元素应该会是最大的数。
3.针对多有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，知道没有任何一对数字需要比较。
图解：
C语言——八大排序
文章图片

代码：

void Bubble_sort(int *arr, int len) { assert(arr != NULL); int tmp = 0; bool swap = false; //加判断条件减少比较次数 for (int i = 0; i < len -1; i++) { for (int j = 0; j < len - 1 - i; j++) { if (arr[j] > arr[j + 1]) { tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; //交换 swap = true; } } if (!swap) { return; } } } void Show(int *arr, int len) { for (int i = 0; i < len; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int drr[] = {1,8,7,5,0}; int num = sizeof(drr) / sizeof(drr[0]); Bubble_sort(drr, num); Show(drr, num); return 0; }

二、选择排序
时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：不稳定（相同的数值都交换了）
主要思路：
每一次从无序组的数据元素中选出最小的一个元素，存放在无序组的起始位置，无需组的元素减少，有序组的元素增加，直到全部待排序的数据元素排完。
图解：
C语言——八大排序
文章图片

代码：
void select_sort(int *arr, int len) { assert(arr != NULL); int i, j; int tmp; int min = 0; for (i = 0; i < len; i++) { int min = i; for (j = i + 1; j < len; j++) { if (arr[j] < arr[min]) { tmp = arr[min]; arr[min] = arr[j]; arr[j] = tmp; } } } } void Show(int *arr, int len) { for (int i = 0; i < len; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int drr[] = { 1,8,7,5,0 }; int num = sizeof(drr) / sizeof(drr[0]); select_sort(drr, num); Show(drr, num); return 0; }

三、插入排序
直接插入排序：
时间复杂度：无序 O(n^2) 有序O(n)
空间复杂度：O(1)
稳定性：稳定
主要思路：
插入排序是最简单常用的方法，将数组分为两部分，排好序的数列，以及未排序的数列，将未排序的数列中的元素 与排好序的数列进行比较，然后将该元素插入到已排序列的合适位置中。
图解：
C语言——八大排序
文章图片

代码：
void Insert_sort(int *arr, int len) { assert(arr != NULL); int i, j; int tmp = 0; for (i = 1; i < len; i++) { tmp = arr[i]; for (j = i - 1; j >= 0; j--) { if (arr[j] > tmp) { arr[j + 1] = arr[j]; } else { break; } } arr[j + 1] = tmp; } }

四、希尔排序：（直接插入的优化）
时间复杂度：O(n^1.5-n^1.5)
空间复杂度：O(1)
稳定性：不稳定
工作原理：
把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
图解：
C语言——八大排序
文章图片

代码：
void Shell(int *arr, int len,int gap) { assert(arr != NULL); int tmp = 0; int i, j; for (i = gap; i < len; i += gap) { tmp = arr[i]; for (j = i - gap; j >= 0; j -= gap) { if (arr[j] > tmp) { arr[j + gap] = arr[j]; } else { break; } } arr[j + gap] = tmp; } } void Shell_sort(int *arr, int len) { int drr[] = { 5,3,1 }; //分组必须是素数最后一个必须为1 int lend = sizeof(drr) / sizeof(drr[0]); for (int i = 0; i < lend; i++) { Shell(arr, len, drr[i]); } }

【C语言——八大排序】五、堆排序
时间复杂度：O(nlog2n)
空间复杂度：O(1)
稳定性：不稳定
主要思路：
1.将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。
2.将其与末尾元素进行交换，此时末尾就是最大值。
3.然后将剩余n -1 个元素重新构造成一个堆，这样会得到n个元素的次小值。
4.如此反复执行，便得到一个有序序列。
图解：
C语言——八大排序
文章图片

代码：
void Adjust(int *arr,int start,int end) { assert(arr != NULL); int tmp = arr[start]; for(int i = 2*start + 1; i <= end; i = 2*i+1) { if(i < end && arr[i] < arr[i + 1])//是否有右孩子 { i++; //最大值的下标 } if(arr[i] > tmp) { arr[start] = arr[i]; start = i; } else { break; } } arr[start] = tmp; } void HeapSort(int *arr,int len) { for(int i = (len - 1 - 1)/2; i >= 0; i--) { Adjust(arr,i,len - 1); } for(int i = 0; i <= len - 1; i++) { int tmp = arr[0]; arr[0] = arr[len - 1 - i]; arr[len - 1 - i] = tmp; Adjust(arr,0,len - 1 - 1 - i); } }

六、快速排序
时间复杂度：最好情况下：O(nlong2n) 最坏情况下：O(n^2)
空间复杂度：O(nlong2n)
稳定性：不稳定
主要思路：
快速排序是找出一个元素（理论上可以随便找一个）作为基准，然后对数组进行分区操作，使基准左边元素的值都不大于基准值，基准右边的值都不小于基准值，如此作为基准的元素调整到排序后的正确位置。递归快速排序，将其他n - 1 个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正确位置，排序完成。所以快速排序算法的核心算法是分区操作，及如何调整基准的位置以及调整返回基准的最终位置以便分治递归。
图解：
C语言——八大排序
文章图片

代码：
//快排的递归 intPartition(int *arr,int left,int right) { int tmp=arr[left]; //将第一个给tmp while(lefttmp)//右边的大于tmp时 { right--; } if(left>=right)//第一次循环完了 { break; } else { arr[left]=arr[right]; } while(left=right) { break; } else { arr[right]=arr[left]; } } arr[left]=tmp; return left; //返回相遇的那个位置 } void Quick(int *arr,int start,int end) { int par=Partition(arr,start,end); if(par>=start+1) { Quick(arr,start,par-1); //当前面部分有两个以上的数时再次排序 } if(parleft+1)//左边有数时入栈 { stack[top++]=left; stack[top++]=par-1; } if(par0)//出栈 { right=stack[--top]; left=stack[--top]; par=Partition(arr,left,right); if(par>left+1) { stack[top++]=left; stack[top++]=par-1; } if(par start+1)//左边是不是有两个数据以上 { Quick(arr,start,par-1); } if(par < end-1) { Quick(arr,par+1,end); } }2.三分取中法 /*void Swap(int *arr,int low,int high) { int tmp = arr[low]; arr[low] = arr[high]; arr[high] = tmp; } void Median_of_Three(int *arr,int start,int mid,int end) {//arr[mid]<=arr[start]<=arrr[end] if(arr[mid] > arr[end])//arr[mid]<=arr[end] { Swap(arr,mid,end); }if(arr[start] < arr[mid])//arr[mid]<=arr[start] { Swap(arr,start,mid); }if(arr[start] > arr[end]) { Swap(arr,start,end); } } void Quick(int *arr,int start,int end) { Median_of_Three(arr,start,(end-start)/2+start,end); int par = Partion(arr,start,end); if(par > start+1)//左边是不是有两个数据以上 { Quick(arr,start,par-1); } if(par < end-1) { Quick(arr,par+1,end); } } 3.聚集相同元素法 void Swap(int *arr,int low,int high) { int tmp = arr[low]; arr[low] = arr[high]; arr[high] = tmp; } void Focus_Same_Num(int *arr, int low, int par, int high, int *left, int *right)//优化4 { int parLeft_Index = par-1; int parRight_Index = par+1; for(int i = par-1; i >= low; i--) { if(arr[i] == arr[par] && i != parLeft_Index) { Swap(arr,i,parLeft_Index); parLeft_Index--; } } *left = parLeft_Index; for(int i = par+1; i <= high; i++) { if(arr[i] == arr[par] && i != parRight_Index) { Swap(arr,i,parRight_Index); parRight_Index++; } } *right = parRight_Index; }void Quick(int *arr,int start,int end) {int par = Partion(arr,start,end); int par_left = par-1; int par_right = par+1; Focus_Same_Num(arr,start,par,end,&par_left,&par_right); if(par > start+1)//左边是不是有两个数据以上 { Quick(arr,start,par-1); }if(par < end-1) { Quick(arr,par+1,end); } }

七、基数排序
时间复杂度：最好情况：O(d(n+rd)) 最坏情况：O(d(r+n)) r代表关键字的基数 d代表长度 n代表关键字的个数
空间复杂度：O(rd+n)
稳定性：稳定
主要思路：
将整数按位数切割成不同的数字，然后按每个位数分别比较。
将所有待比较数值统一为同样的数位长度，数位较短的数前面补0.然后，从最低位开始，依次进行排序。这样从最低位一直到最高位排完序后，数列就变成一个有序序列。
图解：
第一次入桶：按个位数大小
C语言——八大排序
文章图片

第二次入桶：按十位数大小
C语言——八大排序
文章图片

第三次入桶： 按百位数的大小
C语言——八大排序
文章图片

代码：
typedef struct Node { int data; struct Node *next; }Node, *List; //运用单链表 void InitList(List plist)//初始化 { assert(plist != NULL); if (plist == NULL) { return; } plist->next = NULL; } static Node *GetNode(int val) { Node *p = (Node *)malloc(sizeof(Node)); assert(p != NULL); p->data = https://www.it610.com/article/val; p->next = NULL; return p; } bool Insert_tail(List plist, int val)//尾插 { Node *p; for (p = plist; p->next != NULL; p = p->next) { ; } Node *pGet = GetNode(val); p->next = pGet; return true; } bool DeletFirst(List plist, int *rtv)//去掉第一个 { assert(plist != NULL); Node *p=plist->next; if (plist->next == NULL) { return false; } if (rtv != NULL) { *rtv = p->data; } plist->next = p->next; free(p); p = NULL; return true; } int GetMaxBit(int *arr, int len)//获取最大数的位数 { int Max =arr[0]; for (int i = 0; i <= len - 1; i++) { if (arr[i] > Max) { Max = arr[i]; } } int count = 0; while (Max != 0) { count++; Max /= 10; } return count; } int GetNum(int num, int date)//得到num的第date位数字 { for (int i = 0; i < date; i++) { num /= 10; } return num % 10; } void Radix(int *arr, int len, int date) { Node head[10]; for (int i = 0; i < 10; i++) { InitList(&head[i]); } int i; int tmp; for(i = 0; i < len; i++)//入桶 { tmp = GetNum(arr[i],date); Insert_tail(&head[tmp],arr[i]); } i = 0; for(int j = 0; j < 10; )//出桶 { if(DeletFirst(&head[j], &arr[i])) { i++; //出一桶内的数据 } else { j++; //一桶内数据出完后 }} } void RedixSort(int *arr, int len) { int count = GetMaxBit(arr, len); //进出桶多少次 for(int i = 0; i < count; i++) { Radix(arr, len, i); //i表示从右数第0位开始 }

八、归并排序
时间复杂度：O(nlong2n)
空间复杂度：O(n)
稳定性：稳定
主要思想：
将待排序序列R[0…n-1]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。
图解：
C语言——八大排序
文章图片

代码：
void Mearge(int *arr,int len,int gap) { int *brr = (int *)malloc(sizeof(int)*len); //申请空间 assert(brr != NULL); int i = 0; //从第一个开始 int s1 = 0; //指向的一个元素 int e1 = s1 + gap - 1; //指向第一个归并段的最后一个元素 int s2 = e1 + 1; //第二段的第一个元素 int e2 = s2 + gap - 1 < len - 1 ? s2 + gap - 1:len - 1; //判断e2的位置 若超出len 则指向len-1 while(s2 < len)//当前有两个归并端 { while(s1 <= e1 && s2 <= e2) { if(arr[s1] < arr[s2])//第一个归并段的开头与第二个归并段的开头比较 { brr[i++] =arr[s1++]; } else { brr[i++] = arr[s2++]; } } while(s1 <= e1) { brr[i++] = arr[s1++]; } while(s2 <= e2) { brr[i++] =arr[s2++]; } s1 = e2 + 1; //第二次重新合并后重新开始 e1 = s1 + gap - 1; s2 = e1 + 1; e2 = s2 + gap - 1 < len ? s2 + gap -1:len - 1; } while(s1 < len) { brr[i++] = arr[s1++]; } for(int i = 0; i < len; i++) { arr[i] = brr[i]; } free(brr); } void Mearge_Sort(int *arr,int len) { for(int i=1; i

总结：
1. 当n比较小时,可以直接采用直接插入排序或者选择排序；
2.若数据初始状态基本有序（正序），选择直接插入排序、冒泡排序或者快速排序为宜；
3.若n比较大，则采用时间复杂度为O(nlong2n)的排序算法：快速排序、堆排序或者归并排序；
4.快速排序是目前基于比较的排序中被认为最好的方法，当待排关键字是随机分布时，快速排序的平均时间最短；
5.堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况，所以这两个排序实际运用的时候可以比较一下，选择最优的；但是这两种排序都是不稳定的。
6.若要求排序稳定，则可以选用归并排序，但是实际运用的时候通常可以将它和直接插入排序结合使用，先利用直接插入排序求得较长有序子序列，然后再两两归并。

    推荐阅读


    上一篇：c语言时尚编程百例,C语言时尚编程百例

    下一篇：数据结构与算法|数据结构与算法Java（六）——排序算法