快排/堆排/归并/冒泡/

常见的内排序算法

插入排序

直接插入排序

原理：相当于扑克牌变成有序，先拿第一张，把他调节成有序，再拿第二张，与第一张相比找到第二张的位置，再继续拿第三张，以此类推。

void InsertSort(int* arr, int n)
{for (int i = 1; i < n; i++){int end = i - 1;int tmp = arr[i];while (end >= 0){if (tmp < arr[end]){arr[end + 1] = arr[end];arr[end] = tmp;}else{break;}end--;}}
}//时间复杂度为O(N^2),逆序时间复杂度最坏

由于插入排序在有序的时候时间复杂度为O(N),在逆序时时间复杂度为O(N^2),所以如果我们想加快排序的速度，我们可以先对他进行一个预排序，然后再进行一个插入排序。

希尔排序

原理：间隔为gap的分为一组，假设下图的gap为3，总计gap组在这里插入图片描述
也就是说{3，4，1，11}分为一组，{9，5，6，4}和{31，2，6，4}分为一组，依次往前排序，和插入排序很像，都是前面先排好再排下一个

void ShellSort(int* arr, int n)//先搞一个预排的雏形，gap假设为3
{int gap = 1;for (int k = 0; k < gap; k++){for (int j = k; j < n - gap; j += gap){int end = j;int tmp = arr[end + gap];while (end >= 0){if (tmp < arr[end]){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}
}

下面就可以确定gap的取值了

void ShellSort(int* arr, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;//这样gap最后一定是1，相当于一个插入排序for (int k = 0; k < gap; k++){for (int j = k; j < n - gap; j += gap){int end = j;int tmp = arr[end + gap];while (end >= 0){if (tmp < arr[end]){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}}
}

选择排序

void SelectSort(int* arr, int n)
{int begin = 0, end = n - 1;while (begin < end){int maxi = begin;int mini = end;for (int i = begin; i <= end; i++){if (arr[i] > arr[maxi]){maxi = i;}if (arr[i] < arr[mini]){mini = i;}}swap(&arr[begin], &arr[mini]);if (begin == maxi){maxi = mini;}swap(&arr[end], &arr[maxi]);begin++;end--;}
}

堆排

typedef struct heap
{int* arr;int size;int capacity;
}heap;
//向下调整
void AdjustDown(int* arr, int begin, int n)
{int father = begin;int child = 2 * father + 1;while (child<n){if (child + 1 < n && arr[child] < arr[child + 1]){child++;}if (arr[father] < arr[child]){swap(&(arr[father]), &(arr[child]));father = child;child = 2 * father + 1;}else{break;}}
}
//向上调整
void AdjustUp(int* arr, int n, int end)
{int child = end - 1;while (child > 0){if (child + 1 < n && arr[child] < arr[child + 1]){child++;}int father = (child - 1) / 2;if (arr[child] > arr[father]){swap(&(arr[child]), &(arr[father]));}child = father;}
}
//堆初始化
void HeapInit(heap* obj)
{assert(obj);obj->arr = (int*)malloc(sizeof(int) * 4);if (obj->arr == NULL){perror("malloc fail");return;}obj->capacity = 4;obj->size = 0;
}//堆插入
void HeapPush(heap* obj, int val)
{assert(obj);if (obj->size == obj->capacity){int* tmp = (int*)realloc(obj->arr, obj->capacity * 2 * sizeof(int));if (tmp == NULL){perror("malloc fail");return;}obj->arr = tmp;obj->capacity *= 2;}obj->arr[obj->size] = val;obj->size++;AdjustUp(obj->arr, 0, obj->size);
}//堆排序
void HeapSort(int* arr, int n)
{//建大堆for (int i = 0; i < n; i++){AdjustUp(arr, n, i + 1);}for (int i = n - 1; i >= 0; i--){swap(&arr[0], &arr[i]);AdjustDown(arr, 0, i);}
}

交换排序

冒泡排序

void BubbleSort(int* arr, int n)
{for (int i = 0; i < n; i++){bool flag = true;for (int j = 0; j < n - i - 1; j++){if (arr[j] > arr[j + 1]){swap(&arr[j], &arr[j + 1]);flag = false;}}if (flag)break;}
}

由于希尔排序的预排序是一个变化的过程，所以希尔排序的时间复杂度极其复杂，我们记住一个结论，希尔排序的时间复杂度约为O(N^1.3)，要注意的是，希尔排序在最后一次循环中gap必须为1

快速排序

霍尔排序

霍尔排序以数组中某一个数作为基准值，按照该排序把待排序集合分为两部分，这个数左边的值都比这个数小，这个数右边的值都比这个数的大，再用递归重复此过程，设置一个left指针，一个right指针，left指针从0位置开始，right指针从n-1的位置开始，left指针遇到比中间值key大的与right指针遇到比中间值key小的位置交换

int HoareSortPart(int* arr, int begin,int end)
{int left = begin+1, right = end, key = begin;while (left < right){while (left < right && arr[right] >= arr[key]){right--;}while (left < right && arr[left] <= arr[key]){left++;}swap(&arr[left], &arr[right]);}swap(&arr[key], &arr[left]);return left;
}//快速排序 Hoare版本
void HoareSort(int* arr, int begin,int end)
{if (begin >= end){return;}int mid = HoareSortPart(arr, begin, end);HoareSort(arr, begin, mid - 1);HoareSort(arr, mid + 1, end);
}

关于为什么要让right指针先走，归根结底是为了让left指针和right指针相遇的时候，得到的位置所在的值比中间值key要小，我们可以把left指针与right指针相遇分为两种情况，一种是left遇到right指针，另一种是right指针遇到left指针
一.left遇到right指针，因为一个循环是right先走，所以right指针已经遇到了比key小的值，并且还没有交换，所以left遇到right时遇到的就是比key小的数。
二.right指针遇到left指针，因为right指针在走，也就是上一个循环里的left指针已经走完了，并且已经交换了数字，所以left位置的值应该是小于或者等于key的，right再遇到left遇到的就是比key小的数，所以综上所述，无论是left遇到right还是right遇到left，最终得到的数都是小于key或者等于key的。

挖坑法

左右交替选择数，左边left指针选出比key大的值，右边right选出比key小的值，覆盖原来的坑，直到left指针与right指针相遇，再把key放入最后left和right相遇的坑

int HoleSortPart(int* arr, int begin, int end)
{int key = arr[begin];int left = begin, right = end;int hole = begin;while (left < right){while (left < right && arr[right] >= key){right--;}arr[hole] = arr[right];hole = right;while (left < right && arr[left] <= key){left++;}arr[hole] = arr[left];hole = left;}arr[hole] = key;return hole;
}void HoleSort(int* arr, int begin, int end)
{if (begin >= end){return;}int mid = HoleSortPart(arr, begin, end);HoleSort(arr, mid + 1, end);HoleSort(arr, begin, mid - 1);
}

双指针法

cur找小，prev前面的数都比key小，翻滚的往后走

int QuickSortPart(int* arr, int begin, int end)
{int prev = begin, cur = begin + 1;int key = arr[begin];while (cur <= end){if (arr[cur] < key){++prev;swap(&arr[cur], &arr[prev]);}cur++;}swap(&arr[begin], &arr[prev]);return prev;
}void QuickSort(int* arr, int begin, int end)
{if (begin >= end){return;}int mid = QuickSortPart(arr, begin, end);QuickSort(arr, begin, mid - 1);QuickSort(arr, mid+1, end);
}

快排的劣势

快排若每次都取左边的那个数作为中间值时，如果数组有序，快排的时间复杂度会达到O(N^2)，而若每次选取到的是数组的中位数的时候效率是最高的，为了改变这一劣势，我们引入三数取中算法。

三数取中算法

int GetMidIndex(int* arr, int left, int right)
{int mid = (left + right) / 2;if (arr[left] > arr[right]){if (arr[mid] >= arr[left])return left;else if (arr[mid] <= arr[right])return right;elsereturn mid;}else//arr[left]<=arr[right]{if (arr[mid] >= arr[right])return right;else if (arr[mid] <= arr[left])return left;elsereturn mid;}
}

三数取中后的三种快排算法如下，记得要取完值后和begin位置的值互换

int HoareSortPart(int* arr, int begin,int end)
{int left = begin, right = end;int tmp = GetMidIndex(arr, begin, end);swap(&arr[tmp], &arr[begin]);int key = begin;while (left < right){while (left < right && arr[right] >= arr[key]){right--;}while (left < right && arr[left] <= arr[key]){left++;}swap(&arr[left], &arr[right]);}swap(&arr[key], &arr[left]);return left;
}//快速排序 Hoare版本
void HoareSort(int* arr, int begin,int end)
{if (begin >= end){return;}int mid = HoareSortPart(arr, begin, end);HoareSort(arr, begin, mid - 1);HoareSort(arr, mid + 1, end);
}//快速排序 挖坑法版本
int HoleSortPart(int* arr, int begin, int end)
{int tmp = GetMidIndex(arr, begin, end);swap(&arr[tmp], &arr[begin]);int key = arr[begin];int left = begin, right = end;int hole = begin;while (left < right){while (left < right && arr[right] >= key){right--;}arr[hole] = arr[right];hole = right;while (left < right && arr[left] <= key){left++;}arr[hole] = arr[left];hole = left;}arr[hole] = key;return hole;
}void HoleSort(int* arr, int begin, int end)
{if (begin >= end){return;}int mid = HoleSortPart(arr, begin, end);HoleSort(arr, mid + 1, end);HoleSort(arr, begin, mid - 1);
}int QuickSortPart(int* arr, int begin, int end)
{int tmp = GetMidIndex(arr, begin, end);swap(&arr[tmp], &arr[begin]);int prev = begin, cur = begin + 1;int key = arr[begin];while (cur <= end){if (arr[cur] < key){++prev;swap(&arr[cur], &arr[prev]);}cur++;}swap(&arr[begin], &arr[prev]);return prev;
}void QuickSort(int* arr, int begin, int end)
{if (begin >= end){return;}int mid = QuickSortPart(arr, begin, end);QuickSort(arr, begin, mid - 1);QuickSort(arr, mid+1, end);
}

https://leetcode.cn/problems/sort-an-array/
上面那个链接可以用来测排序的算法正不正确，如果你用我上面的代码去这个链接测的话，你会发现有一个数量庞大的都是同一个数字的数组跑不过去，时间复杂度太高了，三数取中可以解决数组有序的问题，但无法解决数组都是同一个数字的问题,所以我、我们还要对此进行改进，我们上面主要是用两路划分，因为我们只分了大于大于key和小于大于key两个部分，我们现在要采取的方法称作三路划分，也就是分为三部分左边那一部分是小于key,中间那部分是等于key的部分，右边那部分是大于key的部分，通过这种方法我们就可以很快的通过全是同一个数的样例，但不建议用递归，因为要传回来两个数，可能会用到数组传参

void ThreeRoadQuickSort(int* arr, int begin, int end)
{if (begin >= end)return;int cur = begin + 1, left = begin, right = end;int tmp = GetMidIndex(arr, begin, end);int key = arr[tmp];while (cur <= right){if (arr[cur] < key){swap(&arr[left], &arr[cur]);left++;}else if (arr[cur] > key){swap(&arr[right], &arr[cur]);right--;}else{cur++;}}ThreeRoadQuickSort(arr, begin, left - 1);ThreeRoadQuickSort(arr, right + 1, end);
}

快排的非递归形式

快排还存在一个风险，如果数字太多，递归层次太深，会有栈溢出的风险，所以我们还是要研究一下快排的非递归的形式

void QuickSortNoR(int* arr, int begin, int end)//1 9
{stack st;InitStack(&st);PushStack(&st, end);PushStack(&st, begin);while (!isemptyStack(&st)){int first = TopStack(&st);PopStack(&st);int last = TopStack(&st);PopStack(&st);int mid = HoareSortPart(arr, first, last);//三种快排part选哪一个都可以if (mid - 1 > first){PushStack(&st, mid - 1);PushStack(&st, first);}if (last > mid + 1){PushStack(&st, last);PushStack(&st, mid+1);}}
}

但大家拿上面那个代码去测试的时候会发现时间复杂度还是超时了，在这里把三数取中改成随机数即可

归并排序

归并排序是将已经有序的子序列合并，也就是先让子序列间有序，再让子序列段间有序，最后将两个有序表合成一个有序表，称为二路归并。

归并排序递归版本

//归并排序 递归版本
void MergeSortPart(int* arr, int begin, int end,int* tmp)
{if (begin == end)//不会存在不存在的区间，所以不需要大于等于return;int mid = (begin + end) / 2;MergeSortPart(arr, begin, mid, tmp);MergeSortPart(arr, mid + 1, end, tmp);int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[i++] = arr[begin1++];}else{tmp[i++] = arr[begin2++];}}while (begin1 <= end1){tmp[i++] = arr[begin1++];}while (begin2 <= end2){tmp[i++] = arr[begin2++];}memcpy(arr + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* arr, int begin, int end)
{if (begin >= end)return;int i = 0;int* tmp = (int*)malloc(sizeof(int) * (end - begin + 1));MergeSortPart(arr, begin, end, tmp);free(tmp);
}//时间复杂度为O(N*logN),空间复杂度为O(N)

归并有一个缺点，比如说我们要分1w个数，分为1250只需要三次，而剩下最后十个要递归要分四次，所以我们可以在这个地方用一个优化，称为小区间优化

void MergeSortPart2(int* arr, int begin, int end, int* tmp)
{if (begin == end)//不会存在不存在的区间，所以不需要大于等于return;if (end - begin + 1 < 10){InsertSort(arr + begin, end - begin + 1);//最好选插入排序而不是冒泡return;}int mid = (begin + end) / 2;MergeSortPart(arr, begin, mid, tmp);MergeSortPart(arr, mid + 1, end, tmp);int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[i++] = arr[begin1++];}else{tmp[i++] = arr[begin2++];}}while (begin1 <= end1){tmp[i++] = arr[begin1++];}while (begin2 <= end2){tmp[i++] = arr[begin2++];}memcpy(arr + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}

上图就是对归并的part的优化，假设把归并排序的调用看做一个二叉树，设这棵树的递归调用次数为2^h-1,而最后一层的递归调用次数就有2 ^(h-1)次，基本上占了调用次数的一半，而倒二层调用2 ^（h-2）次递归调用，占总的递归调用次数的25%，第三层为12.5%，这样的三层最后一层调用下来所要占的递归调用次数达到了87.5%，如果继续扩大数据量去调用其他的排序已经意义不大了

归并排序的非递归版本

归并排序的非递归版本比递归版本复杂很多，是要先选一个一个数，再两组进行对比，再选两个两个数…四个四个数…以此类推，然后再继续两组进行对比，但边界情况的考虑会相对比较麻烦，只有2的次幂才能不考虑边界，如果数组数不是2的次幂则要进行修正，分别有三种情况，我们称第一组的开头和结尾为begin1和end1，第二组为begin2和end2，第一种情况是end1，begin2和end2都越界，第二种情况是begin2和end2越界，第三种情况是end2越界，对于第一种和第二种情况，因为第二组都是完全越界，我们只需要把第一组数据保留拷贝回去即可，所以下面对第二组数据的begin2和end2进行处理，使其无法进入第一个while循环和第三个while循环，第三种情况我们只需要对end2进行修正，因为归并排序是不需要对比的两组数据个数一样的，所以我们可以直接让end2=n-1，即可正常归并

void MergeSortNoR(int* arr, int begin, int end)
{int gap = 1;int n = end - begin + 1;int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}while (gap < n){for (int i = 0; i < n; i+=2*gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;int j = i;int sz = end2 - begin1 + 1;if (end1 >= n||begin2>=n)//对边界进行修正{end1 = n - 1;sz = end1 - begin1 + 1;begin2 = end2 + 1;}else if (end2 >= n){end2 = n - 1;sz = end2 - begin1 + 1;}while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] > arr[begin2]){tmp[j++] = arr[begin2++];}else{tmp[j++] = arr[begin1++];}}while (begin1 <= end1){tmp[j++] = arr[begin1++];}while (begin2 <= end2){tmp[j++] = arr[begin2++];}memcpy(arr + i, tmp + i, sizeof(int) * sz);//归并一组，拷贝一组，这种方法可以用整体拷贝}gap *= 2;}free(tmp);
}

非比较排序计数排序

//计数排序
void CountSort(int* arr, int n)
{int mintmp = arr[0], maxtmp = arr[0];for (int i = 0; i < n; i++){if (arr[i] < mintmp){mintmp = arr[i];}if (arr[i] > maxtmp){maxtmp = arr[i];}}int range = maxtmp - mintmp + 1;int* tmp = (int*)malloc(sizeof(int) * range);if (tmp == NULL){perror("malloc fail");return;}for (int i = 0; i < range; i++){tmp[i] = 0;}for (int i = 0; i < n; i++){tmp[arr[i]-mintmp]++;}int j = 0;for (int i = 0; i < range; i++){while (tmp[i]--){arr[j++] = i + mintmp;}}
}

这个排序的时间复杂度为O(N+range),当range很小的时候，它会很快，但range很大的时候就不一样了，这个排序有两个缺陷，一是这个排序依赖数据范围，二是只能用于整型

稳定性

最后讨论一下排序的稳定性，若有两个数，tmp1和tmp2，且这两个数相等，若排序之前tmp1就在tmp2前，排序后相对位置也不改变，这个排序的稳定性就好。
直接插入排序，冒泡排序，归并排序是稳定的排序。
希尔排序，选择排序（选数稳定，交换时不稳定），堆排序，快速排序是不稳定的排序。

内排序结语

上面所说的全部属于内排序，内排序和外排序最大的区别就是数据量，内排序的数据量较小，可以放在内存中直接排序，而外排序的数据量大，内存装不下，所以要放在磁盘里排序，所以我们接下来将介绍用归并排序对文件里的数据进行排序

外排序

归并排序既可以用作内排序，假设我们将要把40个G的数据进行排序，但内存只有1G，我们就可以把这个40G的大文件分为40个1G的小文件，然后两两排序，合成一个个2G的文件，以此类推，我们在对小文件排序的时候，要使用快排不能用归并，因为一个内存只有1G的空间的情况下，我们用归并会耗费更多的内存，下面是文件排序的代码，里面的n是可以修改的，决定你一个小文件可以放多少个数字

void _FileMergeSort(char* f1, char* f2, char* mf)
{int a1, a2;FILE* File1 = fopen(f1, "r");if (File1 == NULL){printf("open fail");exit(-1);}FILE* File2 = fopen(f2, "r");if (File2 == NULL){printf("open fail");exit(-1);}FILE* mFile = fopen(mf, "w");if (mFile == NULL){printf("open fail");exit(-1);}int flag1 = fscanf(File1, "%d ", &a1);int flag2 = fscanf(File2, "%d ", &a2);while (flag1 != EOF && flag2 != EOF){if (a1 > a2){fprintf(mFile, "%d ", a2);flag2 = fscanf(File2, "%d ", &a2);}else{fprintf(mFile, "%d ", a1);flag1 = fscanf(File1, "%d ", &a1);}}while (flag1 != EOF){fprintf(mFile, "%d ", a1);flag1 = fscanf(File1, "%d ", &a1);}while (flag2 != EOF){fprintf(mFile, "%d ", a2);flag2 = fscanf(File2, "%d ", &a2);}fclose(File1);fclose(File2);fclose(mFile);
}void FileMergeSort()
{FILE* fp;int a = 0;int n = 10;int arr[10];char filename[20];fp = fopen("Sort.txt", "r");int i = 0;int filenames = 0;while (fscanf(fp, "%d ", &a) != EOF){if (i < n - 1)//8{arr[i++] = a;}else{arr[i] = a;QuickSort(arr, 0, sizeof(arr) / sizeof(int) - 1);sprintf(filename, "Sort_%d.txt", filenames++);FILE* tmp = fopen(filename, "w");if (tmp == NULL){printf("error");exit(-1);}for (int j = 0; j < n; j++){fprintf(tmp, "%d ", arr[j]);}i = 0;fclose(tmp);}}//文件归并char mfile[100], file1[100], file2[100];sprintf(file1, "Sort_0.txt");sprintf(mfile, "Sort_sum.txt");for (int i = 1; i < n; i++){sprintf(file2, "Sort_%d.txt", i);_FileMergeSort(file1, file2, mfile);sprintf(file1, mfile);sprintf(mfile, "%d.txt", i);}fclose(fp);
}