图解常用排序算法
排序(Sorting)是数据处理中一种很重要也很常用的运算。一般情况下，排序操作在数据处理过程中要花费很多时间，选对了排序算法，能够提升程序的运行效率。在面试过程中，有关排序算法的面试也是必考点。所以，作为一名开发者，排序算法是一项必备的技能。
排序(Sorting)
排序就是将一组对象按照规定的次序重新排列的过程。
排序可分为两大类：
内部排序(Internal Sorting)：待排序的记录全部存放在计算机内存中进行的排序过程；
外部排序(External Sorting)：待排序的记录数量很大，内存不能存储全部记录，需要对外存进行访问的排序过程。
本文只讨论内部排序。
评价一个排序算法的优劣，主要从时间复杂度和空间复杂度两方面考虑：
时间复杂度：指执行算法所需要的计算工作量，粗略谈就是该算法的运行时间。时间复杂度常用大O符号表示。
空间复杂度：指执行这个算法所需要的内存空间。
当然，仅用执行效率和内存消耗来衡量排序算法的好坏是不够的。针对排序算法，还有一个重要的度量指标：排序算法的稳定性。
排序算法的稳定性：相同键值的两个记录在排序前后的相对位置的变化情况。比如在原序列中，r[i] = r[j]，并且 r[i] 在 r[j] 前面；在排序后的序列中，r[i] 仍在 r[j] 前面，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序的方法有很多，本文主要介绍一下几种：
插入排序
- 直接插入排序
- 希尔排序
交换排序
- 冒泡排序
- 快速排序
选择排序
- 直接选择排序
归并排序
- 有序序列的合并
一、插入排序
常用的插入排序方法有直接插入排序、折半插入排序、表插入排序和希尔排序。本文只介绍直接插入排序和希尔排序。
直接插入排序
直接插入排序(Straight Insertion Sorting)的基本思想是依次将每个记录插入到一个已排序好的有序表中，从而得到一个新的、记录数加 1 的有序表。
void InsertSort(int a[], int n) {
int temp = 0;
//n为表长，从第二个记录起进行插入
for (int i = 1; i < n; i++) {
int j = i - 1;
if (a[i] < a[j]) {
temp = a[i];
a[i] = a[j];
while (temp < a[j-1]) {
a[j] = a[j-1];
j--;
}
a[j] = temp;
}
}
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
int array[] = {45,38,66,90,88,10,25};
int n = sizeof(array)/sizeof(int);
InsertSort(array, n);
printf("排序好的数组为：");
for (int i = 0; i < n; i++) {
printf(" %d", array[i]);
}
printf("\n");
}
return 0;
}
直接插入排序过程如下：
直接插入排序过程示意图.png
直接插入排序算法的时间复杂度为O(n²)，空间复杂度为O(1)。如果待排序记录的数量很大时，一般不选用直接插入排序。
希尔排序
希尔排序(Shell Sort)基本思想是把序列分成若干个小组，然后对每一个小组分别进行插入排序。先取n/2作为第一个增量gap，把序列分组。所有距离为gap的倍数的记录为一组，在各组内进行直接插入排序。然后增量再减半进行分组排序，直到增量为1。
void ShellSort(int a[], int n){
int i;
int j;
int k;
int gap; //gap是分组的增量
int temp;
//增量gap减半
for(gap = n / 2; gap > 0; gap = gap / 2){
for(i = 0; i < gap; i++){
for(j = i + gap; j < n; j = j + gap){ //单独一次的插入排序
if(a[j] < a[j - gap]){
temp = a[j];
k = j - gap;
while(k >= 0 && a[k] > temp){
a[k + gap] = a[k];
k = k - gap;
}
a[k + gap] = temp;
}
}
}
}
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
int array[] = { 5,12,35,11,2,9,41,26,18,4 };
int n = sizeof(array) / sizeof(int);
ShellSort(array, n);
printf("排序好的数组为：");
for (int i = 0; i < n; i++) {
printf("%d ", array[i]);
}
printf("\n");
}
return 0;
}
希尔排序过程如下：
第一步：gap = 10 / 2 = 5，将原序列分组排序：
希尔排序一.png
第二步：gap减半 = 2，将序列继续分组排序：
希尔排序二.png
第三步：gap再减半 = 1，将序列排序得出最后结果：
希尔排序三.png
希尔排序的时间复杂度为O(n*logn)，空间复杂度为O(1)。希尔排序的时间复杂度与选取的增量有关，选取合适的增量可减少时间复杂度。
二、交换排序
交换排序的基本思想是比较两个记录的大小，如果这两个记录的大小出现逆序，就交换这两个记录。这样就把较小的记录往前移动，较大的记录往后移动。
冒泡排序
冒泡排序(Bubble Sorting)是一种交换排序算法，起过程是将第一个记录和第二个记录进行比较，若为逆序则将两个记录交换，然后继续比较第二个和第三个记录。依次比较，直到完成第 n - 1 个记录和第 n 个记录的比较为止。上述过程为第一趟起泡，结果就是将最大的记录移到了第 n 个位置上。然后再进行第二趟起泡排序。重复以上过程，当在一趟起泡过程中没有进行记录交换的操作时，则整个排序过程完成。
//冒泡排序算法
void bubbleSort(int a[], int n) {
for (int i = 0; i<n - 1; i++)
for (int j = 0; j < n - i - 1; j++){
//如果前面的数比后面大，进行交换
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
int array[] = { 5,12,35,11,2,9,41 };
int n = sizeof(array) / sizeof(int);
bubbleSort(array, n);
printf("排序好的数组为：");
for (int i = 0; i < n; i++) {
printf("%d ", array[i]);
}
printf("\n");
}
return 0;
}
冒泡排序过程如下图所示：
冒泡排序过程示意图.png
冒泡排序的时间复杂度为O(n²)，空间复杂度为O(1)。
快速排序
快速排序(Quick Sorting)是交换排序的一种，实质上是对冒泡排序的一种改进。它的基本思想是：在序列中选取一个记录作为基准（通常选取第一个记录作为基准），通过一趟排序将序列分为小于等于基准和大于基准的两部分，然后分别对这两部分记录继续进行快速排序，直到达到整个序列变成有序的序列为止。
//一趟快速排序
int quickPatition(int a[], int left,int right) {
int key = a[left]; //基准元素
while (left < right) {
//从尾端进行比较，将比key小的记录移到左边
while ((left < right) && a[right] >= key) {
right--;
}
a[left] = a[right];
//从首端进行比较，将比key大的记录移到右边
while ((left < right) && a[left] <= key) {
left++;
}
a[right] = a[left];
}
//一趟快速排序结束，将key移到其最终位置
a[left] =key;
return left;
}
//完整快速排序，递归进行快速排序
void quickSort(int *a,int left,int right) {
if (left>=right)
return;
int mid = quickPatition(a,left,right);
quickSort(a, left, mid - 1);
quickSort(a, mid + 1, right);
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
int array[] = { 5,12,35,11,2,9,41,26,18,4 };
int n = sizeof(array) / sizeof(int);
quickSort(array, 0, n - 1);
printf("排序好的数组为：");
for (int i = 0; i < n; i++) {
printf("%d ", array[i]);
}
printf("\n");
}
return 0;
}
快速排序过程如下图所示：
快速排序示意图.png
快速排序时间复杂度为 O(n logn)，空间复杂度为 O(n logn)。
三、选择排序
选择排序(Selection Sorting)基本思想为：每一次在 n - i + 1 个记录中(i = 1，2，...，n - 1)选取最小的记录作为有序序列的第 i 个记录。
本文只介绍直接选择排序。
直接选择排序
直接选择排序基本思想是：在第 i 次选择操作中，通过 n - i 次比较，从 n - i + 1 个记录中选出最小的记录，并和第 i 个记录交换(1 ≤ i ≤ n - 1)。
void SelectSort(int *a, int n) {
//每次循环，选出一个最小的值
for (int i = 0; i < n; i++){
//临时变量用于存放数组最小值的位置
int key = i;
for (int j = i + 1; j < n; j++) {
if (a[j] < a[key]){
//记录数组最小值位置
key = j;
}
}
if (key != i){
//交换最小值，可以用c++的swap()函数替代
int tmp = a[key];
a[key] = a[i];
a[i] = tmp;
}
}
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
int array[] = {45,38,66,90,88,10,25};
int n = sizeof(array) / sizeof(int);
SelectSort(array, n);
printf("排序好的数组为：");
for (int i = 0; i < n; i++) {
printf("%d ", array[i]);
}
printf("\n");
}
return 0;
}
直接选择排序过程如下图所示：
直接选择排序示意图.png
直接选择排序时间复杂度为O(n²)，空间复杂度为O(1)。
四、归并排序
归并排序(Merge Sorting)是将两个或两个以上的有序序列合并成一个新的有序序列。合并的方法是比较各子序列的第一个记录，最小的一个就是排序后新序列的第一个记录。取出这个记录继续比较各子序列现有的第一个记录，便可找出排序后新序列的第二个记录。如此类推，最终可以得出新的序列。
与上文所讲述的插入排序、交换排序、选择排序不同的是，归并排序要求待排序的序列是有若干个有序的子序列组成的。
有序序列的合并
void mergeList(int a[], int aLen, int b[], int bLen, int result[]) {
//p、q为起始位置
int p = 0;
int q = 0;
int i = 0;
while (p < aLen && q < bLen) {
if (a[p] <= b[q]) {
result[i] = a[p];
p++;
}else {
result[i] = b[q];
q++;
}
i++;
}
//a数组有剩余
while (p < aLen) {
result[i] = a[p++];
i++;
}
//b数组有剩余
while (q < bLen) {
result[i] = b[q++];
i++;
}
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
int aArray[] = {5,38,66,80,88,100,125};
int aLength = sizeof(aArray) / sizeof(int);
int bArray[] = {4,6,15,32,44,47,55,73};
int bLength = sizeof(bArray) / sizeof(int);
int newArray[15];
mergeList(aArray, aLength, bArray, bLength, newArray);
printf("排序好的数组为：");
for (int i = 0; i < 15; i++) {
printf("%d ", newArray[i]);
}
printf("\n");
}
return 0;
}
过程示意图如下：
分别取出两个序列第一条记录比较，得出新序列第一条记录为 4 ：
有序序列排序过程示意图1.png
然后 q 往后移动，比较得出，新序列第二条为 5 ，p往后移动。如此类推。
有序序列排序过程示意图2.png
总结
以上几种算法的时间复杂度、空间复杂度、稳定性总结如下图所示。排序算法有很多种，本文只简单介绍了其中几种。后续会为大家持续更新，共同学习更多算法。每种算法的复杂程度不同，针对的数据情况也不同，算法本身没有好坏之分，在一定的数据支持下，选择合适的算法，才能提高程序的运行效率。
算法总结.png
更多技术知识请关注微信公众号
iOS进阶
iOS进阶.jpg
