排序的概念及其运用

(1)排序的概念

排序:所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次 序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排
序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

(2)常见的排序算法

分为插入排序和选择排序，交换排序，以及归并排序
大家好好对比一下区别

测试每个排序的性能

当我们将每个排序的代码写完，我们需要测试一下，每种排序的性能怎么样，就是我们可以用一下我们的时间差，来看每个排序的时间

// 测试排序的性能对比
void TestOP()
{srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);int* a6 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];a6[i] = a1[i];}int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin3 = clock();SelectSort(a3, N);int end3 = clock();int begin4 = clock();HeapSort(a4, N);int end4 = clock();int begin5 = clock();QuickSort(a5, 0, N - 1);int end5 = clock();int begin6 = clock();MergeSort(a6, N);int end6 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("SelectSort:%d\n", end3 - begin3);printf("HeapSort:%d\n", end4 - begin4);printf("QuickSort:%d\n", end5 - begin5);printf("MergeSort:%d\n", end6 - begin6);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);
}

插入排序

直接插入排序其基本思想是

直接插入排序是一种简单的插入排序法，把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为 止，得到一个新的有序序列 。

直接插入排序

我们先写单趟排序，我们最后一个需要排的数，直接插入。
等我们写完单趟排序，然后再写个循环，将其控制起来

我们的单趟排序

void InsertSort(int* a, int n)
{//我们先写单趟排序，假设n个数，//前n-1个数有序，只有最后一个乱序，直接插入//end表示有序数组的最后一个位置的下标,现在我们不知道int end;//将最后一个乱序的数保留下来，防止有序数组向后走将其覆盖int tmp = a[end + 1];//然后遍历一遍，知道将乱序的数放到他的位置//end是下标，是从0开始，所以遍历完数组需要将end>=0while (end >= 0){//假设升序，如果tmpa[end + 1] = a[end];end--;}else{//如果在升序>=a[end],我们就不用动直接跳出来就行了break;}}//跳出来a[end] = tmp;
}

我们在外面套一层循环，然后控制直接插入排序。

void InsertSort(int* a, int n)
{//循环到n-1，就行了，自己画图看一下防止越界。for (int i = 0; i < n ; i++){//我们先写单趟排序，假设n个数，//前n-1个数有序，只有最后一个乱序，直接插入//end表示有序数组的最后一个位置的下标,现在我们不知道int end = i;//将最后一个乱序的数保留下来，防止有序数组向后走将其覆盖int tmp = a[end + 1];//然后遍历一遍，知道将乱序的数放到他的位置//end是下标，是从0开始，所以遍历完数组需要将end>=0while (end >= 0){//假设升序，如果tmpa[end + 1] = a[end];end--;}else{//如果在升序>=a[end],我们就不用动直接跳出来就行了break;}}//跳出来a[end + 1] = tmp;}}

直接插入排序的时间复杂度

有的同学看到两层循环，就直接说是O(N2)O(N^2)O(N2),但是并不是我们要自己分析一下

分为两种情况：
有最好和最坏的情况：
最好的情况是：顺序有序我们的时间复杂度O(N)
最坏的情况是：逆序，我们每个都要进行时间复杂度就是O(N2)O(N^2)O(N2).

希尔排序

什们是希尔排序

希尔排序法又称缩小增量法。
希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个 组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工 作。当到达=1时，所有记录在统一组内排好序。

简而言之就是分为两步
1.预排序（分组排序）
2.插入排序

还是根直接插入排序一样，
将我们先写第一趟的希尔排序的代码。就是先把间距为gap的排好。
我们发现其实和直接插入排序的单趟排序一样，就是将1变为了gap而已，而且只是单趟中的一次交换

//希尔排序
void ShellSort(int* a, int n)
{int gap = 3;int end;//将最后一个乱序的数保留下来，防止有序数组向后走将其覆盖int tmp = a[end + gap];//然后遍历一遍，知道将乱序的数放到他的位置//end是下标，是从0开始，所以遍历完数组需要将end>=0while (end >= 0){//假设升序，如果tmpa[end + gap] = a[end];end -= gap;}else{//如果在升序>=a[end],我们就不用动直接跳出来就行了break;}}//跳出来a[end + gap] = tmp;
}

那们将其变为单趟就再加一层循环，
自己分析一下代码，这是一整趟的希尔排序

//希尔排序
void ShellSort(int* a, int n)
{int gap = 3;for (int j = 0; j < gap; j++){for (int i = j; i < n - gap; i += gap){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

下面将这个简化一下，效率没有任何提升，只是代码更简洁了。

//希尔排序
void ShellSort(int* a, int n)
{int gap = 3;//gap组并排，就是直接按照顺序排，只不过//不像刚才一组一组的。for (int i = 0; i < n - gap; ++i){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}
}

控制gap，实现多趟

//希尔排序
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){//当gap=1的时候就是直接插入排序// 下面两种都是为了让最后一层gap=1.// 只不过第二中效率更高//gap = gap / 2;gap = gap / 3 + 1;//gap组并排，就是直接按照顺序排，只不过//不像刚才一组一组的。for (int i = 0; i < n - gap; ++i){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}}

希尔排序的理解

我们要理解我们的gap的作用
gap>1,就是我们的预排序
gap=1,就是我们的直接插入排序。

我感觉大家跟我第一次学的时候，一样感觉这个有点挫，最后都是是进行直接插入排序吗？为什们不直接用呢？

其实并不是，如果一组数是逆序排列，要排升序，最大的数在最前面，最小的数在最后面，我们要和每个数进行比较，然后才能到他的位置。

而我们希尔排序，利用gap，极大的减轻了他的负担，将大或小的数以gap步向它的位置靠近，让我们最后一次的直接插入排序十分轻松。

对于预排序来说gap有什们要求没有？

1.gap越大，大的数可以更快的到后面，小的可以更快的到前面，却不接近有序。
2.gap越小，数据跳动的越慢，也就越接近有序。

希尔排序的时间复杂度

他其实比较难算，类似于一种期望公式，可以想象一下，就是乱序，越来越变得有序,这种必须那种具有数学很高的素养的人才有可能算出来。我们就估算就可以

我们大概估算约等于O(N1.3)O(N^{1.3})O(N1.3)

选择排序

我们的选择排序有选择排序和堆排序，堆排序我们介绍过了，就不多介绍了，我们主要讲选择排序。

直接选择排序

就是遍历一遍数组，选出最小的，放到第一个，然后再除了第一个选最小的放到开始。

那我们升级一下，再选最小的时候，同时选出最大的，放到开始和结尾，这样就会更快。直接看代码吧，太简单你了。

//直接选择排序
void SelectSort(int* a, int n)
{int begin = 0;int end = n - 1;int min = begin;int max = begin;while (begin < end){for (int i = begin + 1; i <= end; i++){if (a[i] < a[min]){min = i;}if (a[i] > a[max]){max = i;}}Swap(&a[begin], &a[min]);if (max == begin){max = min;}Swap(&a[end], &a[max]);begin++;end--;}}

直接选择排序的时间复杂度

O(N2)O(N^2)O(N2),很简单我们自己分析一下。

堆排序

我们在我们将堆的时候已经写过一会了，我们就不重复了，大家自己看《堆的概念和结构以及堆排序》就可以了。
我给一下这个堆排序的c代码

//交换元素
void Swap(int* p1, int * p2)
{assert(p1 && p2);int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
//向下调整
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] > a[child]){child += 1;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}
void HeapSort(int*a, int n)
{assert(a);for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}for (int i = 0; i < n; i++){Swap(&a[0], &a[n - 1 - i]);AdjustDown(a, n - 1 - i, 0);}
}

交换排序

我们的交换排序，有两种一个是冒泡排序和快速排序

冒泡排序

我们的冒泡排序比直接选择排序还简单，就是注意控制一下循环就好了

//冒牌排序
void BubbleSort(int* a, int n)
{for (int i = 0; i < n -1; i++){for (int j = 1; j <= n - 1 - i; j++){if (a[j] < a[j-1]){Swap(&a[j], &a[j - 1]);}}}
}

快速排序（递归）

快排的单趟排序(升序)

左边的值比key要小，右边的值比key要大。key一般是做左边的值。找两个变量一个控制左，一个控制右。一个叫L，一个叫R。

单趟排序的意义

1.分割出左右区间，左区间比key小，右区间比key大
2.key已经落到他的正确的位置（排序的最终位置）。

剩下的问题

左区间有序，右区间有序，那么整体就ok了。
就是将大问题转换为小问题，用递归解决。

单趟的规定

左边做key，右边先走；能够保证相遇位置比key小。
右边做key，左边先走，能够保证相遇位置比key大。

为什们要这么规定？

会遇到两种情况
1.相遇，一种是R停住，L遇到R。相遇的位置就是R停住的位置
2.相遇，一种是L停住，R遇到L。相遇的位置就是L停住的位置。
因为只有R先走，因为R停住位置小于key，这样才能保证这两个位置都比key小。交换才可以key左边小右边大

快排的单趟排序。

（1） hoare版本

//快速排序
void QuickSort(int* a, int n)
{int left = 0;int right = n - 1;//防止出现下面的问题，将key变成下标//int key = a[left];int key = left;while (left < right){//右边先走，找小//加等于的意思就是我们防止等于key造成死循环//left= a[key]){right--;}//左边再走，找大while (left < right && a[left] <= a[key]){left++;}Swap(&a[left], &a[right]);}//不能跟key换，key是一个局部变量，所以将key成下标，这样就能修改数组。//Swap(&a[left], &key);Swap(&a[left], &a[key]);}

快排递归代码

//快速排序
void QuickSort(int* a, int begin,int end)
{//递归结束条件if (begin >= end){return;}int left = begin;int right = end ;//防止出现下面的问题，将key变成下标//int key = a[left];int key = left;while (left < right){//右边先走，找小//加等于的意思就是我们防止等于key造成死循环//left= a[key]){right--;}//左边再走，找大while (left < right && a[left] <= a[key]){left++;}Swap(&a[left], &a[right]);}//不能跟key换，key是一个局部变量，所以将key成下标，这样就能修改数组。//Swap(&a[left], &key);Swap(&a[left], &a[key]);key = left;//然后就分为了三个区间//[begin,key-1] key [key+1,end]QuickSort(a, begin, key - 1);QuickSort(a, key + 1, end);}

（2）挖坑法

我们挖坑法的思路就是，挖坑填坑的思路
我们先将key的位置挖坑，在挖坑之前将我们的key的下标保存下来，然后我们还是先从右边找比他小的位置，（至于为什们找比它小的位置原理跟上面一样）然后将这个小的位置填到我们前面的坑里，
然后再从左边找比他大的位置，找到后填到上一个坑位中，这样依次类推，我们最后左大于等于右后，就停下来，把我们的key放到坑中，就是这样。

// 挖坑版本的单趟排序
int PartSort2(int* a, int begin, int end)
{int mid = GetMidIndex(a, begin, end);Swap(&a[begin], &a[mid]);int left = begin;int right = end;//防止出现下面的问题，将key变成下标//int key = a[left];int key = a[left];int hole = left;while (left < right){//右边找小，填到坑中while (left < right && a[right] >= key){right--;}a[hole] = a[right];hole = right;//左边找大，填到右边的坑中while (left < right && a[left] <= key){left++;}a[hole] = a[left];hole = left;}a[hole] = key;return hole;
}

（3）双指针

思路:
1.cur找比key小，找到后停下来
2.++pre，交换prev位置和cur位置的值
3.等cur超出数组，我们将pre和key最后交换。

// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{int mid = GetMidIndex(a, left, right);Swap(&a[left], &a[mid]);int key = left;int pre = left;int cur = left + 1;while (cur <= right){if (a[cur] < a[key] && ++pre != cur){Swap(&a[pre], &a[cur]);}cur++;}Swap(&a[pre], &a[key]);key = pre;return key;}

快排的时间复杂度

先算快排的单趟，就是遍历一边数组，就是经典的O(N)。

递归的时间复杂度好像看着代码来分析
我们可以想最好情况和最坏情况分析

最好情况就是：在每次递归的时候都是在key都是在中间。
假设N个值，
这个满二叉树的高度就是log2(N)log_2(N)log2​(N)，每一层看作N
他的时间复杂度就是O(N∗log(N))O(N*log(N))O(N∗log(N))

最坏情况：每次选key都是最大或者最小
实际情况：有序
时间复杂度就是O(N2)O(N^2)O(N2),就是想当于冒泡排序。

快排的空间复杂度

就是算我们创建了多少层栈帧，我们看上面的图知道，创建了O(logN)O(logN)O(logN)个栈帧.我们知道栈帧是可以重复利用的。
所以我们的空间复杂度就是O(logN)O(logN)O(logN)

快排的缺点

当我们的数据是有序，或者接近有序的，我们的快排就会一直占用函数栈帧，导致我们的栈溢出，造成极大的风险。

三数取中法

如果是有序的，我们的key就不需要动，就一直要递归，最终造成栈溢出，并且他这时的效率就会很低。
我们选中间的的数，然后跟key交换，就可以很好的解决这个问题

//三数取中
//beigin  mid end
int GetMidIndex(int* a, int begin, int end)
{int mid = (begin + end) / 2;if (a[begin] < a[mid]){if (a[mid] < a[end]){return mid;}else if (a[begin]>a[end]){return begin;}else{return end;}}else//begin>mid{if (a[mid] > a[end]){return mid;}else if (a[begin] < a[end]){return begin;}else{return end;}}
}
//快速排序
void QuickSort(int* a, int begin,int end)
{//递归结束条件if (begin >= end){return;}int mid = GetMidIndex(a, begin, end);Swap(&a[begin], &a[mid]);int left = begin;int right = end ;//防止出现下面的问题，将key变成下标//int key = a[left];int key = left;while (left < right){//右边先走，找小//加等于的意思就是我们防止等于key造成死循环//left= a[key]){right--;}//左边再走，找大while (left < right && a[left] <= a[key]){left++;}Swap(&a[left], &a[right]);}//不能跟key换，key是一个局部变量，所以将key成下标，这样就能修改数组。//Swap(&a[left], &key);Swap(&a[left], &a[key]);key = left;//然后就分为了三个区间//[begin,key-1] key [key+1,end]QuickSort(a, begin, key - 1);QuickSort(a, key + 1, end);}

加入三数取中后的时间复杂度

使用三数取中以后，快排瞬间从最坏变成最好
快排几乎不会出现最坏的情况
快排的时间复杂度就是O(N∗logN)O(N*logN)O(N∗logN)

小区间优化(减少递归次数)

我们当递归到最后，分割分割，假设剩10个数，光递归高度最少也得4次，而且高度越低，结点越多，假设高度是h，那最后一层的递归调用2h−12^h-12h−1
就是我们杀鸡用牛刀，即浪费了空间，又浪费了时间。

所以当数据量小的时候，我们既不用的了递归了，我们用直接插入排序。

我们的减少区间的代码就是在快速排序的递归条件中加一个条件，如果我们递归的数小于15个数，我们就用直接插入排序。

	//小区间优化,减少递归调用//因为是闭区间，所以要加1if ((end - begin + 1) < 15){InsertSort(a + begin, end - begin + 1);}else{int key = PartSort3(a, begin, end);QuickSort(a, begin, key - 1);QuickSort(a, key + 1, end);}

快速排序（非递归）

我们的非递归就是，还是用他的单趟排序，和递归的思路还是一样，而我们的递归就是传我们的区间。

我们非递归的重点就是将区间保存下来，我们的思路就是用栈将区间保存下来，至于怎么保存，大家看看代码。重要的就是利用了栈的功能。

/快排（非递归）
void QuickSortNonR(int* a, int begin, int end)
{ST st;StackInit(&st);StackPush(&st, begin);StackPush(&st, end);while (!StackEmpty(&st)){int right = StackTop(&st);StackPop(&st);int left = StackTop(&st);StackPop(&st);//进行单趟排序int key = PartSort1(a, left, right);//[left,key-1][key][key+1,right]if (key + 1 < right){StackPush(&st, key + 1);StackPush(&st, right);}if (left < key - 1){StackPush(&st, left);StackPush(&st, key - 1);}}StackDestroy(&st);
}

归并排序

归并排序（递归）

归并的单趟思想

归并的思想

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；
即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

所以我们写单趟排序，就是将两个有序的数组，合并成一个有序的数组。
这就是我们的大思路。

注意：我们再归并两个数组的时候，我们不能修改原数组，如果将原本的内容覆盖，我们就不能进行比较了，所以我们创建一个临时数组，将比较的内容放到临时数组上然后在拷贝到原数组。

归并递归代码

//归并排序的子函数
void _MergeSort(int* a, int left, int right, int* tmp)
{//结束条件if (left >= right){return;}//分割左右两部分int mid = (left + right) / 2;// [0~mid] [mid+1~right]//递归将其变有序_MergeSort(a, left, mid, tmp);_MergeSort(a, mid + 1, right, tmp);//这是经过递归就会产生两个有序的数组//而归并的单趟就是将两个有序的数组合并成一个有序的数组//我们就不要用上面的变量了，重新定义一个int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int n = left;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[n++] = a[begin1++];}else{tmp[n++] = a[begin2++];}}while (begin1 <= end1){tmp[n++] = a[begin1++];}while(begin2 <= end2){tmp[n++] = a[begin2++];}memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
}// 归并排序递归实现
void MergeSort(int* a, int n)
{//创建一个数组，就是防止我们在递归的过程中产生覆盖int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");exit(-1);}_MergeSort(a, 0, n - 1, tmp);
}

归并排序的时间复杂度和空间复杂度

时间复杂度:O(N∗logN)O(N*logN)O(N∗logN)
空间复杂度:O(N)

空间复杂度：也要算栈帧，但是logNlogNlogN可以忽略不记

归并排序（非递归）

我们快排，是用栈，是因为他是前序
而我们的递归是后序，就不能用这个。

我们就控制每个区间就可以归并了，因为归并是二分。
我们的区间可以很好的控制，不想快排不是二分控制不了。

但是思路简单，但是代码是什们复杂的
rangeN表示每组归并的数据个数

归并非递归代码

// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");exit(-1);}//归并每组的数据个数，从1开始，因为认为1个数是有序的，就可以直接归并int rangeN = 1;while (rangeN < n){for (int i = 0; i < n; i += 2 * rangeN){//[begin1,end1] [begin2,end2]//将上面归并的内容拿下来int begin1 = i, end1 = i + rangeN - 1;int begin2 = i + rangeN, end2 = i + 2 * rangeN - 1;int n = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[n++] = a[begin1++];}else{tmp[n++] = a[begin2++];}}while (begin1 <= end1){tmp[n++] = a[begin1++];}while (begin2 <= end2){tmp[n++] = a[begin2++];}//归并一部分，拷贝一部分memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}}free(tmp);tmp = NULL;
}

非递归代码问题

我们合并两个有序数组的时候，我们需要控制区间，但是我们的两个区间并没有进行控制，就会发生溢出，导致程序的崩溃。

经过分析，共有三种越界
分别是：
1.end1越界，begin2越界，end2越界
2.begin2越界，end2越界
3.end2越界

非递归正确代码

// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");exit(-1);}//归并每组的数据个数，从1开始，因为认为1个数是有序的，就可以直接归并int rangeN = 1;while (rangeN < n){for (int i = 0; i < n; i += 2 * rangeN){//[begin1,end1] [begin2,end2]//将上面归并的内容拿下来int begin1 = i, end1 = i + rangeN - 1;int begin2 = i + rangeN, end2 = i + 2 * rangeN - 1;printf("[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);int j = i;// end1 begin2 end2 越界if (end1 >= n){break;}else if (begin2 >= n){break;}else if (end2 >= n){end2 = n - 1;}while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}//归并一部分，拷贝一部分memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}rangeN *= 2;}free(tmp);tmp = NULL;
}

排序比较

选择排序的稳定性：不稳定
举例：