1.前言

排序算法算是算法中的重中之重，也是面试和工作中的最常用的算法之一。现在我们就来结合例子，一个个分析各大算法的特点。

选择一个算法，其实主要是根据待排序的数据特征来选的，一般是在时间复杂度、空间复杂度和算法稳定性之间做取舍。

1.1 冒泡排序

1.1.2 改进后的冒泡排序

1.2 快速排序

1.2.2快速排序算法的改进

1.3 插入排序

1.4 希尔排序

1.5 选择排序

1.6 堆排序

1.7 归并排序

4 举例对比各个算法的效率

2.各个算法比较

3.例子分析（C语言版本）

3.1 冒泡排序

3.1.1 普通冒泡排序

每一轮结束，选择一个未排序数组中最大的一个放到数组最后。

//普通冒泡排序
void bubblesort1(char *s) {
int len = strlen(s);
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < len - i - 1; j++) {
if (s[j] > s[j + 1]) {
char temp = s[j];
s[j] = s[j + 1];
s[j + 1] = temp;
}
}
}
}

3.1.2 改进后的冒泡排序

选出最大数放到后面，再选最小数放到前面，如此反复，直到左边界和右边界重合。
当数组中有已排序好的数时，这种排序比传统冒泡排序性能稍好。

//改进后的冒泡排序
void bubblesort2(char *s) {
int len = strlen(s);
int left = 0;
int right = len - 1;
while (left < right) {
for (int i = left; i < right; i++) {
if (s[i] > s[i + 1]) {
char temp = s[i + 1];
s[i + 1] = s[i];
s[i] = temp;
}
}
right--;
for (int j = right; j >= left; j--) {
if (s[j] > s[j + 1]) {
char temp = s[j + 1];
s[j + 1] = s[j];
s[j] = temp;
}
}
left++;
}
}

3.2 快速排序

指定数组或者某部分的最后一个元素作为基准值，随机快速排序指定数组或者某一部分中的随机值作为基准值。

1.快速排序可能是应用最为广泛的排序算法了。特点是实现简单、适用于各种不同的输入数据，且应用中比其他排序算法要快得多。
2.原地排序，所需的时间和$nlogn$成正比。
3.方法的关键在于切分，排序效率最终依赖切分数组的效果。

在切分不平衡时程序可能会极为低效。 例如，如果第一次从最大的元素切分，第二次从第二小的元素切分，如此这般，每次调用只会移除一个元素。这会导致一个大数组需要切分很多次。

//快速排序1
void swap(char *a, char *b) {
char temp = *a;
*a = *b;
*b = temp;
}
int patition(char *a, int left, int right) {
int j = left; //用来遍历数组
int i = j - 1;//指向小于基准元素的位置
char key = a[right];//基准元素，一般是数组的最后一个元素
//从左到右遍历数组，把小于等于基准元素的放到左边位置，大于基准元素的放到右边位置
for ( ; j < right; ++j) {
if (a[j] < key) {
swap(&a[j], &a[++i]);//这个++i很玄学
}
}
swap(&a[right], &a[++i]);//将基准元素放到中间
//返回基准元素的位置
return i;
}
void quicksort(char *s, int left, int right) {
if (left >= right) {
return;
}
int mid = patition(s, left, right);
quicksort(s, 0, mid - 1);
quicksort(s, mid + 1, right);
}

//快速排序2
void quicksort2(char *s, int left, int right) {
if (left >= right) {
return;
}
int j = left; //用来遍历数组
int i = j - 1;//指向小于基准元素的位置
char key = s[right];//基准元素，一般是数组的最后一个元素
//从左到右遍历数组，把小于等于基准元素的放到左边位置，大于基准元素的放到右边位置
for (; j < right; ++j) {
if (s[j] < key) {
//swap(&a[j], &a[++i]);//这个++i很玄学
char temp = s[j];
s[j] = s[++i];
s[i] = temp;
}
}
//swap( &a[right], &a[++i]);//将基准元素放到中间
char temp = s[right];
s[right] = s[++i];
s[i] = temp;
//返回基准元素的位置int mid = patition(s, left, right);
quicksort2(s, 0, i - 1);
quicksort2(s, i + 1, right);
}

3.2.1快速排序算法的改进

如果我们的排序代码会被执行很多次，或被用在大型数组上，那么通过以下的改进可能将性能提升20%-30%。

方法：熵最优排序
将数组切分为三部分，分别对应小于、等于和大于切分元素的数组元素。

//快速排序算法3----三向切分的快速排序
void quicksort3(char *s, int lo, int hi) {
if (hi <= lo) return;
int lt = lo, i = lo + 1, gt = hi;
char v = s[lo];//基准元素
char temp;
while (i <= gt) {
if (s[i] < v) {
temp = s[lt];
s[lt++] = s[i];
s[i++] = temp;
}
else if (s[i] > v) {
temp = s[i];
s[i] = s[gt];
s[gt--] = temp;
}
else {
i++;
}//这样s[lo .. lt-1] < v = s[lt .. gt] < s[gt + 1 .. hi]了
quicksort3(s, lo, lt - 1);
quicksort3(s, gt + 1, hi);
}
}

注意：所有的快速排序算法，使用数据的中位数来切分数组将会获得很大的改进。

3.3 插入排序

将数组的第一个数认为是有序数组，从后往前（从前往后）扫描该有序数组。把数组中其余n-1个数，根据数值的大小，插入到有序数组中，直至数组中的所有数有序排列为止。

插入排序代码很简洁，也很好理解。

//插入排序
void insertsort(char *s) {
int len = strlen(s);
for (int i = 0; i < len; i++) {
int j = i;
while ((j > 0) && s[j] < s[j - 1]) {
char temp = s[j];
s[j] = s[j - 1];
s[j - 1] = temp;
j--;
}
}
}

3.4 希尔排序

实质：插入排序的改。
背景：对于大规模乱序数组插入排序很慢，因为它只交换相邻的元素。
思想：希尔排序使得数组中任意间隔为$h$的元素都是有序的，然后再逐渐减小$h$，直至$h$为1。

//希尔排序
void shellsort(char *s) {
int len = strlen(s), i, j;
char temp;
int gap;
for (gap = len / 2; gap >= 1; gap /= 2) { //初始步长为数组长度的一半，之后步长减半
for (i = 0 + gap; i < len; i += gap) {//对数组进行插入排序，gap为1时结束
temp = s[i];
j = i - gap;
while (j >= 0 && s[j] > temp) {
s[j + gap] = s[j];
j -= gap;
}
s[j + gap] = temp;
}
}
}

对于有经验的程序员，有时会选择希尔排序，因为对于中等大小的数组它的运行时间是可以接受的。它的代码量很小，且不需要使用额外的内存空间。其他高校的排序算法，可能只会比希尔排序快两倍（可能还不到），而且很复杂。如果需要解决一个排序问题而又没有系统排序算法可以使用（如直接接触硬件或嵌入式系统），可以先用希尔排序，之后再考虑是否值得替代为其他更加复杂的排序算法。

3.5 选择排序

1.找到数组中最小的那个元素；
2.将它和数组的第一个元素交换位置；
3.在剩下的元素中找到最小的元素；
4.将它与数组的第二个元素交换位置；
5.以此类推。

//选择排序
void selectsort(char *s) {
int len = strlen(s);
for (int i = 0; i < len; i++) {
int key = i;//临时变量，用于存放后面数组中最小元素的位置
for (int j = i + 1; j < len; j++) {
if (s[j] < s[key]) {
key = j; //记录数组最小位置的值
}
}
if (key != i) {
char tmp = s[key];
s[key] = s[i];
s[i] = tmp;
}
}
}

3.6 堆排序

把数组构造成一个大顶堆（父亲节点大于其子节点），然后把堆顶（数组最大值，数组第一个元素）和数组最后一个元素交换，这样就把最大值放到了数组最后边。

以此类推。

//堆排序
/*
1.创建大堆顶，i为当前节点，n为堆的大小
2.从第一个非叶子节点i从下往上，从右到左调整结构
3.从两个儿子节点中选择较大的那个，与父节点进行比较
4.如果儿子节点比父节点大，则进行交换
*/
void creatheap(char *s, int i, int n) {
//数组是从0开始计数，所以左节点为2*i+1，右节点为2*i+2
for (; i >= 0; --i) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int j = 0;
//选出左右子节点中较大的那一个
if (right < n) {
s[left] > s[right] ? j = left : j = right;
}
else {
j = left;
}
//交换子节点与父节点
if (s[j] > s[i]) {
char tmp = s[i];
s[i] = s[j];
s[j] = tmp;
}
}
}
//进行堆排序，依次选出最大值放到最后面
void heapsort(char *s) {
//初始化构造堆
int len = strlen(s);
creatheap(s, len / 2 - 1, len);
//交换第一个元素和最后一个元素后，堆的大小减一
for (int j = len - 1; j >= 0; j--) {
//最后一个元素和第一个元素进行交换
char tmp = s[0];
s[0] = s[j];
s[j] = tmp;
int i = j / 2 - 1;
creatheap(s, i, j);
}
}

3.7 归并排序

在归并操作上的一种有效的排序算法,该算法是采用分治法。
先使每个子序列有序，再使子序列段间有序。

//归并排序
//合并两个已经拍好序的数组
void Merge(char *s, int left, int mid, int right) {
int len = right - left + 1;
//数组长度
char *temp = new char[len];
//分配一个临时数组
int k = 0;
int i = left;
//前一个数组的起始元素
int j = mid + 1;
//后一个数组的起始元素
while (i <= mid && j <= right) {
//选择较小的存入临时数组
temp[k++] = s[i] <= s[j] ? s[i++] : s[j++];
}
while (i <= mid) {
temp[k++] = s[i++];
}
while (j <= right) {
temp[k++] = s[j++];
}
for (int k = 0; k < len; k++) {
s[left++] = temp[k];
}
}
//递归实现归并排序
void MergeSort(char *s, int left, int right) {
if (left == right) {
return;
}
int mid = (left + right) / 2;
MergeSort(s, left, mid);
MergeSort(s, mid + 1, right);
Merge(s, left, mid, right);
}

4.举例对比各个算法的效率（C语言）

下面通过一段C语言程序来对比各个排序算法所花费的时间，对字符串数组s1,s2和s3进行排序。

#include<string.h>
#include <stdio.h>
#include <time.h>
#define _CRT_SECURE_NO_DEPRECATE；
#define _CRT_SECURE_NO_WARNINGS；
#define SWAP(X,Y) X=X+Y;Y=X-Y;X=X-Y
void bubblesort1(char *s);
void bubblesort2(char *s);
void quicksort(char *s, int left, int right);
int patition(char *a, int left, int right);
void swap(char *a, char *b);
void quicksort2(char *s, int left, int right);
void quicksort3(char *s, int lo, int hi);
void insertsort(char *s);
void shellsort(char *s);
void selectsort(char *s);
void creatheap(char *s, int i, int n);
void heapsort(char *s);
void Merge(char *s, int left, int mid, int right);
void MergeSort(char *s, int left, int right);
int main()
{
int start;
start = clock();
char s1[] = "abcfed";
char s2[] = "bcadfe";
char s3[] = "fshskbbsadasdaafsdgfgntyasfafasfahsfkasfapqipowejq1231nkdsk,1213";
int len_s1 = sizeof(s1) / sizeof(char);
int len_s2 = sizeof(s2) / sizeof(char);
int len_s3 = sizeof(s3) / sizeof(char);
//bubblesort1(s1);
//bubblesort1(s2);
//bubblesort1(s3);
//bubblesort2(s1);
//bubblesort2(s2);
//bubblesort2(s3);
//quicksort(s1, 0, strlen(s1) - 1);
//quicksort(s2, 0, strlen(s2) - 1);
//quicksort(s3, 0, strlen(s3) - 1);
//quicksort2(s1, 0, strlen(s1) - 1);
//quicksort2(s2, 0, strlen(s2) - 1);
//quicksort2(s3, 0, strlen(s3) - 1);
//quicksort3(s1, 0, strlen(s1) - 1);
//quicksort3(s2, 0, strlen(s2) - 1);
//quicksort3(s3, 0, strlen(s3) - 1);
//insertsort(s1);
//insertsort(s2);
//insertsort(s3);
//shellsort(s1);
//shellsort(s2);
//shellsort(s3);
//selectsort(s1);
//selectsort(s2);
//selectsort(s3);
//heapsort(s1);
//heapsort(s2);
//heapsort(s3);
MergeSort(s1, 0, strlen(s1) - 1);
MergeSort(s2, 0, strlen(s2) - 1);
MergeSort(s3, 0, strlen(s3) - 1);
for (int i = 0; i < strlen(s1); i++) {
printf("%c ", s1[i]);
}
printf("n");
for (int i = 0; i < strlen(s2); i++) {
printf("%c ", s2[i]);
}
printf("n");
for (int i = 0; i < strlen(s3); i++) {
printf("%c ", s3[i]);
}
printf("n");
if (strcmp(s1, s2) == 0) {
printf("
1 ");
}
else {
printf(" -1 ");
}
printf("n");
printf("%d ", len_s1);
printf("%d ", len_s2);
printf("%d ", len_s3);
printf("n");
printf("%d ", strlen(s1));
printf("%d ", strlen(s2));
printf("%d ", strlen(s3));
printf("n");
printf("这段代码一共花费的时间为：");
printf("%dmsn", clock() - start);
getchar();
return 0;
}
//普通冒泡排序
void bubblesort1(char *s) {
int len = strlen(s);
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < len - i - 1; j++) {
if (s[j] > s[j + 1]) {
char temp = s[j];
s[j] = s[j + 1];
s[j + 1] = temp;
}
}
}
}
//改进后的冒泡排序
void bubblesort2(char *s) {
int len = strlen(s);
int left = 0;
int right = len - 1;
while (left < right) {
for (int i = left; i < right; i++) {
if (s[i] > s[i + 1]) {
char temp = s[i + 1];
s[i + 1] = s[i];
s[i] = temp;
}
}
right--;
for (int j = right; j >= left; j--) {
if (s[j] > s[j + 1]) {
char temp = s[j + 1];
s[j + 1] = s[j];
s[j] = temp;
}
}
left++;
}
}
//快速排序1
void swap(char *a, char *b) {
char temp = *a;
*a = *b;
*b = temp;
}
int patition(char *a, int left, int right) {
int j = left; //用来遍历数组
int i = j - 1;//指向小于基准元素的位置
char key = a[right];//基准元素，一般是数组的最后一个元素
//从左到右遍历数组，把小于等于基准元素的放到左边位置，大于基准元素的放到右边位置
for ( ; j < right; ++j) {
if (a[j] < key) {
swap(&a[j], &a[++i]);//这个++i很玄学
}
}
swap(&a[right], &a[++i]);//将基准元素放到中间
//返回基准元素的位置
return i;
}
void quicksort(char *s, int left, int right) {
if (left >= right) {
return;
}
int mid = patition(s, left, right);
quicksort(s, 0, mid - 1);
quicksort(s, mid + 1, right);
}
//快速排序2
void quicksort2(char *s, int left, int right) {
if (left >= right) {
return;
}
int j = left; //用来遍历数组
int i = j - 1;//指向小于基准元素的位置
char key = s[right];//基准元素，一般是数组的最后一个元素
//从左到右遍历数组，把小于等于基准元素的放到左边位置，大于基准元素的放到右边位置
for (; j < right; ++j) {
if (s[j] < key) {
//swap(&a[j], &a[++i]);//这个++i很玄学
char temp = s[j];
s[j] = s[++i];
s[i] = temp;
}
}
//swap( &a[right], &a[++i]);//将基准元素放到中间
char temp = s[right];
s[right] = s[++i];
s[i] = temp;
//返回基准元素的位置int mid = patition(s, left, right);
quicksort2(s, 0, i - 1);
quicksort2(s, i + 1, right);
}
//快速排序算法3----三向切分的快速排序
void quicksort3(char *s, int lo, int hi) {
if (hi <= lo) return;
int lt = lo, i = lo + 1, gt = hi;
char v = s[lo];//基准元素
char temp;
while (i <= gt) {
if (s[i] < v) {
temp = s[lt];
s[lt++] = s[i];
s[i++] = temp;
}
else if (s[i] > v) {
temp = s[i];
s[i] = s[gt];
s[gt--] = temp;
}
else {
i++;
}//这样s[lo .. lt-1] < v = s[lt .. gt] < s[gt + 1 .. hi]了
quicksort3(s, lo, lt - 1);
quicksort3(s, gt + 1, hi);
}
}
//插入排序
void insertsort(char *s) {
int len = strlen(s);
for (int i = 0; i < len; i++) {
int j = i;
while ((j > 0) && s[j] < s[j - 1]) {
char temp = s[j];
s[j] = s[j - 1];
s[j - 1] = temp;
j--;
}
}
}
//希尔排序
void shellsort(char *s) {
int len = strlen(s), i, j;
char temp;
int gap;
for (gap = len / 2; gap >= 1; gap /= 2) { //初始步长为数组长度的一半，之后步长减半
for (i = 0 + gap; i < len; i += gap) {//对数组进行插入排序，gap为1时结束
temp = s[i];
j = i - gap;
while (j >= 0 && s[j] > temp) {
s[j + gap] = s[j];
j -= gap;
}
s[j + gap] = temp;
}
}
}
//选择排序
void selectsort(char *s) {
int len = strlen(s);
for (int i = 0; i < len; i++) {
int key = i;//临时变量，用于存放后面数组中最小元素的位置
for (int j = i + 1; j < len; j++) {
if (s[j] < s[key]) {
key = j; //记录数组最小位置的值
}
}
if (key != i) {
char tmp = s[key];
s[key] = s[i];
s[i] = tmp;
}
}
}
//堆排序
/*
1.创建大堆顶，i为当前节点，n为堆的大小
2.从第一个非叶子节点i从下往上，从右到左调整结构
3.从两个儿子节点中选择较大的那个，与父节点进行比较
4.如果儿子节点比父节点大，则进行交换
*/
void creatheap(char *s, int i, int n) {
//数组是从0开始计数，所以左节点为2*i+1，右节点为2*i+2
for (; i >= 0; --i) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int j = 0;
//选出左右子节点中较大的那一个
if (right < n) {
s[left] > s[right] ? j = left : j = right;
}
else {
j = left;
}
//交换子节点与父节点
if (s[j] > s[i]) {
char tmp = s[i];
s[i] = s[j];
s[j] = tmp;
}
}
}
//进行堆排序，依次选出最大值放到最后面
void heapsort(char *s) {
//初始化构造堆
int len = strlen(s);
creatheap(s, len / 2 - 1, len);
//交换第一个元素和最后一个元素后，堆的大小减一
for (int j = len - 1; j >= 0; j--) {
//最后一个元素和第一个元素进行交换
char tmp = s[0];
s[0] = s[j];
s[j] = tmp;
int i = j / 2 - 1;
creatheap(s, i, j);
}
}
//归并排序
//合并两个已经拍好序的数组
void Merge(char *s, int left, int mid, int right) {
int len = right - left + 1;
//数组长度
char *temp = new char[len];
//分配一个临时数组
int k = 0;
int i = left;
//前一个数组的起始元素
int j = mid + 1;
//后一个数组的起始元素
while (i <= mid && j <= right) {
//选择较小的存入临时数组
temp[k++] = s[i] <= s[j] ? s[i++] : s[j++];
}
while (i <= mid) {
temp[k++] = s[i++];
}
while (j <= right) {
temp[k++] = s[j++];
}
for (int k = 0; k < len; k++) {
s[left++] = temp[k];
}
}
//递归实现归并排序
void MergeSort(char *s, int left, int right) {
if (left == right) {
return;
}
int mid = (left + right) / 2;
MergeSort(s, left, mid);
MergeSort(s, mid + 1, right);
Merge(s, left, mid, right);
}

注意

不要以为某一个排序算法所用的时间短，就说这个算法比其他好。因为：

1. 有的算法适合小规模数组排序（冒泡排序、插入排序），有的算法适合大规模数据排序（快速排序，堆排序）。
2. 快速排序很脆弱，如果你能将待排序树组的中位数作为排序中的关键值的话，快速排序的所需时间将会指数级下降。
3. 善于利用和改进排序算法，将会在面试和工作中加分不少。

最后

以上就是单薄战斗机为你收集整理的经典算法之（常见）排序算法的比较1.前言4 举例对比各个算法的效率2.各个算法比较3.例子分析（C语言版本）4.举例对比各个算法的效率（C语言）的全部内容，希望文章能够帮你解决经典算法之（常见）排序算法的比较1.前言4 举例对比各个算法的效率2.各个算法比较3.例子分析（C语言版本）4.举例对比各个算法的效率（C语言）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。