常见排序算法总结
本文对比较常用且比较高效的排序算法进行了总结和解析，并贴出了比较精简的实现代码，包括选择排序、插入排序、归并排序、希尔排序、快速排序等。算法性能比较如下图所示：
1 冒泡排序
基本原理
这里介绍升序的原理，从数组的第一个元素arr[0]开始，两两比较(arr[n],arr[n+1])，如果前面的数大于后面的数（arr[n] > arr[n+1]）,那么交换两个元素的位置，把大的数往后移动。这样依次经过一轮比较以后，最大的数将会被交换到最后的位置（arr[n-1]）。算法的时间复杂度为O(n^2)。下面是升序的步骤：
数组排序前 7 23 12 4 33 21 2 17 13 9
第一轮排序 7 12 4 23 21 2 17 13 9 33 (10个数，但实际第一次只需要交换9次)
第二轮排序 7 4 12 21 2 17 13 9 23
第三轮排序 4 7 12 2 17 13 9 21
第四轮排序 4 7 2 12 13 9 17
第五轮排序 4 2 7 12 9 13
第六轮排序 2 4 7 9 12
第七轮排序 2 4 7 9
第八轮排序 2 4 7
第九轮排序 2 4
降序同理，但是把小的数往后移动，经过一轮比较以后，最小的数将会被交换到最后的位置（arr[n-1]）。下面是降序的步骤：
数组排序前 7 23 12 4 33 21 2 17 13 9
第一轮排序 23 12 7 33 21 4 17 13 9 2
第二轮排序 23 12 33 21 7 17 13 9 4
第三轮排序 23 33 21 12 17 13 9 7
第四轮排序 33 23 2 1 17 13 12 9
第五轮排序 33 23 21 17 13 12
第六轮排序 33 23 21 17 13
第七轮排序 33 23 21 17
第八轮排序 33 23 21
第九轮排序 33 23
程序示例
#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;
#define swap(x,y) x=x+y,y=x-y,x=x-y
enum sortTyepe
{
UP,
Down
};
void BubbleSort(int arr[], int n, sortTyepe type)
{
int i, j;
int exchange = 1; //交换标志
for (i = 0; i < n - 1; i++) //最多做n-1趟排序
{
exchange = 0; //本趟排序开始前，交换标志应为假
for (j = 0; j < n - 1 - i; j++) //对当前无序区R[i..n]自下向上扫描
{
if (type == UP) //升序
{
if (arr[j] > arr[j + 1])
{
swap(arr[j + 1], arr[j]); //交换记录
exchange = 1; //发生了交换，故将交换标志置为真
}
}
else if (type == Down) //降序
{
if (arr[j] < arr[j + 1])
{
swap(arr[j + 1], arr[j]); //交换记录
exchange = 1; //发生了交换，故将交换标志置为真
}
}
}
if (!exchange) //本趟排序未发生交换，提前终止算法
return;
}
}
int main()
{
int i = 0;
int arr[] = { 7, 23, 2, 4, 33, 21, 2, 17, 13, 9 };
int len = sizeof(arr) / sizeof(arr[0]);
BubbleSort(arr, len, UP);
for (; i<len; i++)
printf("%d ", arr[i]);
printf("\n");
BubbleSort(arr, len, Down);
for (i=0; i<len; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
/*
输出结果：
2 2 4 7 9 13 17 21 23 33
33 23 21 17 13 9 7 4 2 2
*/
2 快速排序
基本原理
快速排序是对冒泡排序的一种改进，其基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
一趟快速排序的具体做法为：设置两个索引start和end分别指向待排序列的开始和结尾，记录下基准值baseval(待排序列的第一个记录)，然后先从start所指的位置向前搜索直到找到一个小于baseval的记录，接着从end所指向的位置向后搜索直到找到一个大于baseval的记录，将这两个索引指向的数据进行交换，重复这三个步骤直到low=high为止。
程序示例
#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;
void quickSort(int arr[], int start, int end)
{
int i, j, t, baseval;
if (start > end) //递归，直到start = end为止
return;
baseval = arr[start]; //基准数
i = start;
j = end;
while (i != j)
{
//从右向左找比基准数小的数 （要先从右边开始找）
while (arr[j] >= baseval && i < j)
j--;
//从左向右找比基准数大的数
while (arr[i] <= baseval && i < j)
i++;
if (i < j)
{
//交换两个数在数组中的位置
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
//最终将基准数归位
arr[start] = arr[i];
arr[i] = baseval;
quicksort(arr, start, i - 1);//继续处理左边的，这里是一个递归的过程
quicksort(arr, i + 1, end);//继续处理右边的 ，这里是一个递归的过程
}
int main()
{
int i = 0;
int arr[] = { 2, 1, 5, 6, 3, 4, 7, 9, 0, 8 };
int len = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, len-1);
//输出排序后的结果
for (; i<len; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
/*
输出结果：
0 1 2 3 4 5 6 7 8 9
*/
总结
快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，它的平均时间复杂度为O(NlogN)。
3 直接选择排序
基本原理
对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将该记录与该轮”第一个记录“的位置进行交换；接着对不包括第一个记录以外的其他记录进行第二轮比较，得到最小的记录并与第二个记录进行位置交换；重复该过程，直到进行比较的记录只有一个时为止（升序）。算法的时间复杂度为O(n^2)。以数组{2, 1, 5, 6, 3, 4, 7, 9, 0, 8}为例，具体步骤如下：
第一轮排序后：0 [1 5 6 3 4 7 9 2 8]
第二轮排序后：0 1 [5 6 3 4 7 9 2 8]
第三轮排序后：0 1 2 [6 3 4 7 9 5 8]
第四轮排序后：0 1 2 3 [6 4 7 9 5 8]
第五轮排序后：0 1 2 3 4 [6 7 9 5 8]
第六轮排序后：0 1 2 3 4 5 [7 9 6 8]
第七轮排序后：0 1 2 3 4 5 6 [9 7 8]
第八轮排序后：0 1 2 3 4 5 6 7 [9 8 ]
第九轮排序后：0 1 2 3 4 5 6 7 8 [9]
程序示例
#include <stdio.h>
//选择排序_从小到大
void SelectSort(int *a, int n)
{
int i, j;
int min = 0;
int index = 0;
int temp;
for (i = 0; i < n - 1; i++) //排序n-1次
{
min = a[i]; //min设置为每轮中的第一个数
index = i; //index设置为每轮中的第一个位置
for (j = i + 1; j < n; j++)
{
//找到每轮中最小的数，赋给temp
if (a[j] < min)
{
min = a[j];
index = j;
}
}
//将每轮中最小的值与每轮中第一个位置(i)的值进行交换
if (index != i) //如果这轮中最小的值刚好在第一个位置，就不用交换了
{
min = a[index];
a[index] = a[i]; //每轮中第一个位置的值，赋给该轮最小位置处，形成交换
a[i] = min; //将每轮中最小的值依次赋给a[i]，形成交换
}
}
}
int main()
{
int i = 0;
int arr[] = { 2,1,5,6,3,4,7,9,0,8 };
int len = sizeof(arr) / sizeof(arr[0]);
SelectSort(arr, len);
for (; i < len; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
/*
输出结果：
0 1 2 3 4 5 6 7 8 9
*/
总结
从简单选择排序的过程来看，它的特点就是交换移动数据次数相当少，这样也就节约了相应的时间。无论是最好情况，还是最差情况，其比较次数都是一样的，第i趟排序需要进行n-i 次。而对于交换次数而言，最好的情况是有序，需要交换0次；最差的情况，即逆序时，交换次数为n-1次，基于最终的排序时间是比较与交换的次数总和，因此总的时间复杂度依然为O(n^2)。
4 直接插入排序
基本原理
直接插入排序法的排序原则是：将一组无序的数字排列成一排，左端第一个数字为已经完成排序的数字，其他数字为未排序的数字。然后从左到右依次将未排序的数字插入到已排序的数字中。算法的时间复杂度为O(n^2)。
例如要将数组arr=[4,2,8,0,5,1]排序，可以将4看做是一个有序序列(图中用蓝色标出)，将[2,8,0,5,1]看做一个无序序列。无序序列中2比4小，于是将2插入到4的左边，此时有序序列变成了[2,4]，无序序列变成了[8,0,5,1]。无序序列中8比4大，于是将8插入到4的右边，有序序列变成了[2,4,8],无序序列变成了[0,5,1]。以此类推，最终数组按照从小到大排序。
程序示例
#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;
// 插入排序
void insertSort(int arr[], int length)
{
int i; //用来遍历无序序列
int j; //用来遍历有序序列
int temp; //定义一个临时变量，用于交换数据时存储
//最开始无序队列的起始位置索引为1
for (i = 1; i < length; i++) //要对无序序列的每一个元素，在有序序列进行插入，所以我们会对无序序列进行遍历
{
//第二层循环主要用于对有序序列进行扫描，和无序序列中要插入进来的数据进行逐一比较，然后决定插入到哪里
for (j = 0; j<i; j++)
{
//升序，则将有序序列中的较大值与无序序列中的较小值进行交换，降序则相反
if (arr[j]>arr[i])
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
int main()
{
int i = 0;
int arr[] = { 2, 1, 5, 6, 3, 4, 7, 9, 0, 8 };
int len = sizeof(arr) / sizeof(arr[0]);
insertSort(arr, len);
//输出排序后的结果
for (; i<len; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
/*
输出结果：
0 1 2 3 4 5 6 7 8 9
*/
参考：