八大排序（附代码）

八大排序

直接插入排序希尔排序选择排序堆排序冒泡排序快速排序归并排序计数排序 直接插入排序

令end=i，记录a[end+1]的值为x。若a[end]>x,则a[end+1]=a[end],end- -;当end减到小于0时，再让a[end+1]=x（如图，将降序成升序）。

void InsertSort(int* a, int n){for (int i = 0; i < n - 1; i++){int end = i;int x = a[end + 1];while (end >= 0){if (a[end] > x){a[end+1] = a[end];end--;}else{break;}}a[end + 1] = x;}}

希尔排序

基本思想：希尔排序是基于直接插入的，是直接插入排序的优化。直接插入排序是当前数值与后一个数值相比；但再希尔排序中，是当前数值与相隔gap个数值相比，然后让gap不断缩小（一般让gap/=2），直到gap等于1时，就是直接插入排序，在gap==1之前，都是预排序，由于预排序的存在，使得数组的大部分数据不用再交换（即不用走if循环，而直接break），使得直接插入排序优化，这就称为“希尔排序”。

void ShellSort(int* a, int n){int gap = n;while (gap > 1){//gap越大，排的越快，越不接近有序//gap越小，拍的越慢，越接近有序//最后gap==1，数组已经接近有序，基本不用进if (a[end] > x)，直接可以break结束while循环。gap /= 2;//gap也可以这样// gap=gap/3+1//直接插入排序的变形，只不过不是int x = a[end + 1];而是int x = a[end + gap];for (int i = 0; i < n - gap; i++){int end = i;int x = a[end + gap];while (end >= 0){if (a[end] > x){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = x;}}}

选择排序

基本思想：每一次从待排序的数据元素中选出最小和最大的元素，分别存放在序列的起始位置和末尾位置，然后缩小边界，重复此过程，直到 left>=right,所以元素就排完了。

//交换函数void Swap(int* x, int* y){int tmp = *x;*x = *y;*y = tmp;}//选择排序void SlectSort(int* a, int n){int left = 0;int right = n - 1;while (left < right){int small = left;int big = left;for (int i = left+1; i <= right; i++){if (a[small] > a[i]){small = i;}if (a[i] > a[big]){big = i;}}Swap(&a[left], &a[small]);if (big == left)// 当最大的数字就是在下标为left的位置上时，由于上一个swap，将最大的数值换到了下标为small的位置上，因此要修正一下big的下标big = small;Swap(&a[right], &a[big]);left++;right--;}}

堆排序

基本思想：堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。（这里排升序升序）

先建大堆

排序，树顶元素跟最后一个叶子加换，则最大的元素就再序列的末尾位置，这个最大的元素之和就不参与后续的运算，再向下调整建堆，重复此过程，完成排序。

//交换函数void Swap(int* x, int* y){int tmp = *x;*x = *y;*y = tmp;}//向下调整void AdjustDown(int *a,int parent, int n){int child = parent * 2 + 1;while (child a[child]){child++;}//不够优化//if (a[child] > a[parent])//{//Swap(&a[parent], &a[child]);//}//parent = child;//child = parent * 2 + 1;if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}//向下调整建堆void CreatHeap(int* a, int n){//这个parent的下标不对//int parent = (n - 1) / 2;int parent = (n - 1 - 1) / 2;//最后一个父亲结点while (parent >= 0){AdjustDown(a,parent,n);parent--;}}//堆排序void HeapSort(int* a, int n){CreatHeap(a, n);while (n > 0){//注意下标是n-1；Swap(&a[0], &a[n-1]);n--;AdjustDown(a, 0, n);}}

冒泡排序

由此图可得出结论，若有n个数，需要n-1趟排序；第一趟需要对比交换n-1次，第二趟要对比交换n-2次，以此类推。

void BubbleSort(int* a, int n){int i = 0;for (i = 0; i < n - 1; i++)//要排多少趟{int j = 0;int flag = 1;for (j = 0; j < n - 1 - i; j++)//每一趟的交换行为{if (a[j] > a[j + 1]){Swap(&a[j], &a[j + 1]);flag = 0;}}if (flag)//如果flag==1，说明没有交换过，则有序了，就不用再排，break跳出循环break;}}

快速排序

基本思想：再序列中选一个关键值key，让序列中<=key的元素排在key的左边，>=key的元素排在key的右边。为保证key的值不为序列的最小值或最大值，尽可能为序列的中间值，还使用了GetMidIndex函数。

//确保key不是最小或者是最大的数int GetMidIndex(int* a, int left, int right){//int mid = (left + right) / 2;int mid = left + ((right - left) >> 1);if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else // a[left] > a[mid]{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}}int pation1(int* a, int left, int right){// 三数取中 -- 面对有序最坏情况，变成选中位数做key，变成最好情况int key = GetMidIndex(a, left, right);Swap(&a[left], &a[key]);key = left;while (left < right){while (left= a[key]){right--;}while (left < right && a[left] <= a[key]){left++;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[key]);return left;}//快速排序void QuickSort(int* a, int left, int right){if (left >= right){return;}//当区间太小时，还用递归就得不偿失了，可以用直接其他排序让子区间有序，11.18日 1：13：00,有了这个if就可以不用什么那个ifif (right - left+1 < 10)//right - left + 1为区间个数{//因为left和right是闭区间，而InsertSort第二个参数是元素个数，所以加1。InsertSort(a + left, right - left + 1);}else{int key = pation4(a, left, right);QuickSort(a, left, key - 1);//递归排关键值左边的数QuickSort(a, key + 1, right);//递归排关键值右边的数}}

归并排序

基本思想：将两个有序的数组合并成一个有序的数组。

那怎么将一个无序的序列，分为两个有序的序列呢？通过不断的递归，使得最终的两个序列只有一个元素，再合并成一个只有2个元素的有序序列；然后通过不断的返回，最终变成两个有序的序列，再合成一个有序的序列。

void _MergeSort(int* a, int left, int right,int* tmp){if (left >= right){return;}int mid = (left + right) / 2;_MergeSort(a, left, mid, tmp);_MergeSort(a, mid + 1, right, tmp);//自己写的时候不知道怎么把两个数组归并到tmp中，即不知道怎么控制tmp的下标//int i = left;//int j = mid + 1;//while (i <= mid && j <= right)//{//if (a[i] > a[j])//{//tmp[] = a[i];//i++;//}//else//{//tmp[] = a[j];//j++;//}//}int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int i = left;while(begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}for (int j = left; j <= right; j++){a[j] = tmp[j];}}//归并排序void MergeSort(int* a, int n){int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){printf("malloc failn");exit(-1);}_MergeSort(a, 0, n - 1, tmp);free(tmp);tmp = NULL;}

计数排序

基本思想：开一个数组a，当有n个x，就让下标为x的值为n，然后检索新开的数组排序。

//计数排序void CountSort(int* a, int n){int small = a[0];int big = a[0];for (int i = 0; i < n; i++){if (a[i] < small){//不是small=i；small = a[i];}if (a[i] > big){//不是big=i；big = a[i];}}//注意要加1int range = big - small+1;//当序列是1000-1100的数时，那么a[1000]之前就没有元素，我们不必开这么多的空间，我们就只要开（big - small+1）个空间（即range），例如1000有3个，tmp[0]为3，最终排序的时候tmp+1000来排序int* tmp = (int*)malloc(sizeof(int) * range);memset(tmp, 0, sizeof(int) * range);for (int i = 0; i < n; i++){//不是a[i]-range；tmp[a[i]-small]++;}int j = 0;for (int i = 0; i < range; i++){while (tmp[i]--){//不是i+rangea[j++] = i + small;}}}