目录

一.排序的概念

二.常见排序算法的实现

2.1 插入排序

  （1）直接插入排序：

  当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移！

（2）希尔排序：

2.2选择排序

 （1） 直接选择排序:

（2）堆排序

2.3交换排序

（1）冒泡排序

（2）快速排序

  a.挖坑法

 思路：先取出最左侧数据，保存在临时变量key中（作为基准值），此时最左侧由于数据被取走，所以此时就像一个坑位，下标用pivot表示，然后我们定义出begin和end变量，分别位于数组的左右两侧，end从右往左走，如果遇到比key值小的，就将该数据填入到坑位（num【pivot】）中,然后这里就变成了新的坑位，坑位以右的全是比key值大的；这时候begin向右走，遇到比key值大的就停下，将这个值填入到刚才的坑位中，以后就这样循环，end走完begin走，每次走完都要更新坑位，直到begin和end相遇为止；

3.begin往右走的时候遇到了大于key的值停下来了，end往左走的时候没有遇到小于key的，一直走到了begin：

  对于这种情况，begin停下来后必然进行了一次坑位更新，此时begin就是一个没有数据的坑位，当end到达坑位后，说明坑位右侧必然是全都大于key，左侧必然全都小于key，所以，我们应该将key保存在这个坑位处；

b.左右指针法

​编辑

 思路：和挖坑法有相似处，也是选取最左侧为基准值key，定义begin和end在左右两侧，end在向左走的时候遇到小于key的就停下，begin向右走的时候遇到大于key的也停下，双方此时交换一下元素，然后继续重复上述过程，直到相遇；

代码实现：

c.前后指针法

d.快速排序的非递归实现

2.4.归并排序

递归实现  

非递归实现

三.排序算法复杂度及稳定性分析

---

一.排序的概念

  1. 排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

  2.稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

  3.内部排序：数据元素全部放在内存中的排序。

  4.外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

二.常见排序算法的实现

  

2.1 插入排序

  基本思想：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

  （1）直接插入排序：

  当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移！

代码实现：

void insertSort(int* num, int n)
{for (int i = 0; i < n - 1 ; i++){int end = i;int tmp = num[end + 1];for (end = i; end >= 0; end--){if (num[end] > tmp){num[end + 1] = num[end];}else{break;}}num[end + 1] = tmp;}}

直接插入排序的特性总结：

  1. 元素集合越接近有序，直接插入排序算法的时间效率越高

  2. 时间复杂度：O(N^2)   

  3. 空间复杂度：O(1)，它是一种稳定的排序算法

  4. 稳定性：稳定

（2）希尔排序：

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

图解：

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。

2. 当gap > 1时都是预排序（有间隔的插入排序），目的是让数组更接近于有序。当gap == 1时，就相当于直接插入排序，此时数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。

3.稳定性：不稳定

代码实现：

void shellSort(int* num, int n)
{int gap = n/2;while (gap >= 1){for (int i = 0; i < n - gap; i ++){int end = i;int tmp = num[end + gap];while (end >= 0){if (num[end] > tmp){num[end + gap] = num[end];end -= gap;}else break;}num[end + gap] = tmp;}gap /= 2;}}

2.2选择排序

  基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

 （1） 直接选择排序:

    在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素，若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换，在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素。

代码实现：

void selectSort(int* num, int n)
{for (int begin = 0, end = n - 1; begin < end; begin++, end--){int max_id = begin, min_id = begin;for (int i = begin; i <= end; i++){if (num[i] > num[max_id]){max_id = i;}if (num[i] < num[min_id]){min_id = i;}}swap(num[begin], num[min_id]);if (max_id == begin){max_id = min_id;}swap(num[end], num[max_id]);}
}

直接选择排序的特性总结：

  1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用

  2. 时间复杂度：O(N^2)

  3. 空间复杂度：O(1)

  4. 稳定性：不稳定

（2）堆排序

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

  思路：先把数组构建成一个堆，然后依次取出堆顶元素，与数组末尾元素交换，然后自堆顶向下调整；

  代码：

void adjustDown(int* num, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && num[child + 1] > num[child]){child++;}if (num[child] > num[parent]){swap(num[child], num[parent]);parent = child;child = 2 * parent + 1;}else{break;}}
}
void heapSort(int *num,int n)
{for (int i = (n - 1 - 1) / 2; i >= 0; i--){adjustDown(num, n, i);}for (int end = n-1; end > 0; end--){swap(num[0], num[end]);adjustDown(num, end, 0);}
}

堆排序的特性总结：

1. 堆排序使用堆来选数，效率就高了很多。

2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(1)

4. 稳定性：不稳定

2.3交换排序

  基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

（1）冒泡排序

  冒泡排序（假设是升序）就是从左往右对所有数据依次进行两两比较进行交换，最终将最大的数据交换到了最右边，这个过程就像冒泡泡一样，最大值就是一个泡泡，经过n-1次冒泡后，整个排序也就完成了！

  代码实现：

void bubbleSort(int* num, int n)
{for (int i = 0; i < n - 1; i++){int flag = 1;for (int j = 0; j < n - i - 1; j++){if (num[j] > num[j + 1]){flag = 0;swap(num[j], num[j + 1]);}}if (flag){break;}}
}

 冒泡排序的特性总结：

  1. 冒泡排序是一种非常容易理解的排序

  2. 时间复杂度：O(N^2) 

  3. 空间复杂度：O(1)

  4. 稳定性：稳定

（2）快速排序

  基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后对左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

  将区间按照基准值划分为左右两半部分的常见方式有：

  a.挖坑法

 思路：先取出最左侧数据，保存在临时变量key中（作为基准值），此时最左侧由于数据被取走，所以此时就像一个坑位，下标用pivot表示，然后我们定义出begin和end变量，分别位于数组的左右两侧，end从右往左走，如果遇到比key值小的，就将该数据填入到坑位（num【pivot】）中,然后这里就变成了新的坑位，坑位以右的全是比key值大的；这时候begin向右走，遇到比key值大的就停下，将这个值填入到刚才的坑位中，以后就这样循环，end走完begin走，每次走完都要更新坑位，直到begin和end相遇为止；

  对于begin和end相遇，我们可以分析出以下几种情况：

1.end刚开始在往左走的时候一直没有遇到小于key的值，没有停下来就走到了begin处：

  这种情况其实就是数组已经有序了，最后begin和end都为0；基准值就该在最左侧；

2.end遇到了小于key的值停下来后，begin没有遇到大于key的值，一直走到了end处：

  对于这种情况，end停下来后必然进行了一次坑位更新，此时end就是一个没有数据的坑位，当begin到达坑位后，说明坑位左侧必然是全都小于key，右侧必然全都大于key，所以，我们应该将key保存在这个坑位处；

3.begin往右走的时候遇到了大于key的值停下来了，end往左走的时候没有遇到小于key的，一直走到了begin：

  对于这种情况，begin停下来后必然进行了一次坑位更新，此时begin就是一个没有数据的坑位，当end到达坑位后，说明坑位右侧必然是全都大于key，左侧必然全都小于key，所以，我们应该将key保存在这个坑位处；

  综上三种情况，当begin与end相遇后，都会形成一个新的坑位，这个坑位就是key值应该在的位置，填入进去即可；

代码实现：

  

void quickSort1(int* num, int left, int right)
{if (right <= left) return;int begin = left, end = right;int mid = (left + right) / 2;int id = Getmid(begin, end, mid);swap(num[id], num[begin]);int pivot = begin;int key = num[pivot];while (begin < end){while (begin < end && num[end] >= key){end--;}num[pivot] = num[end];pivot = end;while (begin < end && num[begin] <= key){begin++;}num[pivot] = num[begin];pivot = begin;}pivot = begin;num[pivot] = key;quickSort1(num, left, pivot - 1);quickSort1(num,pivot+1, right);
}

b.左右指针法

 思路：和挖坑法有相似处，也是选取最左侧为基准值key，定义begin和end在左右两侧，end在向左走的时候遇到小于key的就停下，begin向右走的时候遇到大于key的也停下，双方此时交换一下元素，然后继续重复上述过程，直到相遇；

此时的相遇也做一下情况讨论:

1.刚开始end畅通无阻地到达了begin，即begin = end = 0，说明基准值就该在最左侧；

2.end停下来后，begin一直走到了end处：

  end停下来的位置一定是小于key的，这个时候begin一直走到了end处，说明end左侧全是小于key的，右侧全是大于key的，只有脚下的数是小于key的；

3.begin停下来后，end一直走到了begin处：

  begin停下来后的位置元素一定是大于key的，而end所在的元素必然小于key，此时要和end所在的元素进行交换，这样begin所在的元素就是小于key的了，这就导致接下来的end一直走到了begin处，说明begin左侧全是小于key的，右侧全是大于key的，只有脚下的数是于key的；

代码实现：

void quickSort2(int* num, int left, int right)
{if (right <= left)return;int begin = left, end = right;int mid = (left + right) / 2;int id = Getmid(begin, end, mid);swap(num[id], num[begin]);int key = begin;while (begin < end){while (begin < end && num[end] >= num[key]){end--;}while (begin < end && num[begin] <= num[key]){begin++;}swap(num[begin], num[end]);}swap(num[key], num[begin]);quickSort2(num, left, begin - 1);quickSort2(num, begin+1, right);
}

c.前后指针法

  和前面两种方法不同，这里定义prev和cur，分别位于首元素和第二元素处；这里是想要将数据从第二位置处开始记录，cur从左往右走，只要遇到小于key的元素，就让prev++，然后交换num[prev]和num[cur]，这样，cur走完以后，prev以及prev左侧的数据全都是小于key的了，这时将key与num[prev]交换即可；

  代码实现：

void quickSort3(int* num, int left, int right)
{if (right <= left)return;int prev = commonPart(num, left, right);int begin = left, end = right;int mid = (left + right) / 2;int id = Getmid(begin, end, mid);swap(num[id], num[begin]);int key = begin;int prev = left, cur = left + 1;while (cur <= right){if (num[cur] < num[key] && cur != ++prev){swap(num[prev], num[cur]);}cur++;}swap(num[key], num[prev]);quickSort3(num, left, prev - 1);quickSort3(num, prev+1, right);
}

d.快速排序的非递归实现

  我们之前的做法都是让基准值回到应该在的位置后，然后选出左右区间来递归执行；

  如果要用非递归的方式，就要借助栈来实现，先将数组的左右端点入栈，注意入栈顺序是右端点、左端点，因为栈的后进先出特性，先拿出的是左端点；

  然后，出栈两次就能拿到要操作区间的左右端点，进行基准值的定位后，将新的右区间入栈，左区间入栈，如果区间长度小于等于1就不入栈；这样，只要栈不为空，我们就可以像递归方式一样

进行每个区间的基准值定位了；

  代码实现：

int commonPart(int* num, int left, int right)
{int begin = left, end = right;int mid = (left + right) / 2;int id = Getmid(begin, end, mid);swap(num[id], num[begin]);int key = begin;int prev = left, cur = left + 1;while (cur <= right){if (num[cur] < num[key] && cur != ++prev){swap(num[prev], num[cur]);}cur++;}swap(num[key], num[prev]);return prev;
}

void quickSort4(int* num, int left, int right)
{stack<int> st;st.push(right);st.push(left);while (!st.empty()){int begin = st.top(); st.pop();int end = st.top(); st.pop();int prev = commonPart(num, begin, end);if (prev + 1 < end){st.push(end);st.push(prev + 1);}if (begin < prev-1 ){st.push(prev - 1);st.push(begin);}}
}

快排最坏情况的两种典型场景（On2）

  1.数组已经有序（升序或降序）

  当输入数组已经有序时，如果每次选择第一个或最后一个元素作为基准值，每次分区只能减少一个元素。例如：对于数组[1, 2, 3, 4, 5]，选择第一个元素1作为基准值，分区后左边为空，右边为[2, 3, 4, 5]递归树会退化为链表，深度为n，总比较次数为n + (n-1) + (n-2) + … + 1 = n(n+1)/2

  2.所有元素相同

当数组中所有元素都相等时，如果分区策略不当，也会导致极度不均衡的分区

例如：数组[5, 5, 5, 5, 5]，如果基准值选择和分区实现不当，可能导致每次只减少一个元素

可以通过合理选择基准值来规避这种风险

 快速排序优化

1. 三数取中法选key

  三数取中法的核心思想是从待排序数组中选择三个元素，通常是首元素、中间元素和末元素，然后取这三个元素的中位数作为基准值(pivot)。这种方法可以有效避免在数组已经有序或接近有序时出现的最坏情况。

代码实现：

int Getmid(int x, int y, int k)
{int max = x, min = x;if (y > x) max = y;if (k > x) max = k;if (y < min) min = y;if (k < min) min = k;return x + y + k - max - min;
}

2. 递归到小的子区间时，可以考虑使用插入排序  

快速排序的特性总结：

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序

2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(logN)

4. 稳定性：不稳定

2.4.归并排序

基本思想：

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

递归实现  

归并排序说到底就是合并两个有序的序列，但是我们如何将数组变成两个有序序列呢？可以采用找中间下标，分成左右区间分别递归的方式，递归到最后就是两个元素的区间排序，一个元素肯定是有序序列了，因此此时可以做合并，从下往上回调，最后整个数组就会变成有序序列了！

  代码实现：

void MergeSort(int* num, int left, int right, int* tmp)
{if (right <= left)return;int mid = (left + right) / 2;int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;MergeSort(num, begin1, end1, tmp);MergeSort(num, begin2, end2, tmp);int index = left;while (begin1 <= end1 && begin2 <= end2){if (num[begin1] < num[begin2]){tmp[index++] = num[begin1++];}else{tmp[index++] = num[begin2++];}}while (begin1 <= end1){tmp[index++] = num[begin1++];}while (begin2 <= end2){tmp[index++] = num[begin2++];}for (int i = left; i <= right; i++){num[i] = tmp[i];}}
void mergeSort1(int* num, int n)
{int* tmp = new int[n];MergeSort(num, 0, n - 1, tmp);
}

非递归实现

  再回忆一下归并排序的思路，首先我们要将数组变成两个有序序列，然后将他们合并起来即可；

关键点是怎么得到两个有序序列，从递归的思路不难看出，我们是要从底层慢慢构建出有序序列的，即先进行区间大小为1的有序序列合并，这样就获得了大小为2的有序序列，再进行大小为2的有序序列合并，就得到了大小为4的有序序列……依次类推即可；

  随着要合并的有序序列区间的增大，难免会出现区间端点超出数组范围的情况，下面分情况讨论：

  1.左区间的右端点超出范围或右区间的左端点超出范围，此时左区间内的数据已经有序了，因此无需合并；

  2.右区间的左端点合法，但右端点超范围，此时要将右端点改为数组的右端点，然后进行左右区间的合并；

代码实现：

void _mergesort(int* num, int begin1, int end1, int begin2, int end2,int *tmp)
{int index = begin1;int left = begin1, right = end2;while (begin1 <= end1 && begin2 <= end2){if (num[begin1] < num[begin2]){tmp[index++] = num[begin1++];}else{tmp[index++] = num[begin2++];}}while (begin1 <= end1){tmp[index++] = num[begin1++];}while (begin2 <= end2){tmp[index++] = num[begin2++];}for (int i = left; i <= right; i++){num[i] = tmp[i];}
}
void mergeSort2(int* num, int n)
{int* tmp = new int[n];int gap = 1;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;if (begin2 >= n){break;}if (end2 >= n){end2 = n - 1;}_mergesort(num, begin1, end1, begin2, end2, tmp);}gap *= 2;}
}

归并排序的特性总结：

1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。

2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(N)

4. 稳定性：稳定

三.排序算法复杂度及稳定性分析