八大排序算法性能对比及复杂度分析
性能对比
其实上面讲的这几个算法，我们通过对他们的理解以及时间复杂度就能分辨出来那些算法效率更高。
接下我给出一个程序，让它们对一组大量的相同的数组进行排序，我们打印出它们执行的时间，给大家展示一下（程序的具体实现大家可以不用关心，直接拿去用）：
void TestOP()
{
srand(time(0));
const int N = 10000;
int* a1 = (int*)malloc(sizeof(int) * N);
if (a1 == NULL)
exit(-1);
int* a2 = (int*)malloc(sizeof(int) * N);
if (a2 == NULL)
exit(-1);
int* a3 = (int*)malloc(sizeof(int) * N);
if (a3 == NULL)
exit(-1);
int* a4 = (int*)malloc(sizeof(int) * N);
if (a4 == NULL)
exit(-1);
int* a5 = (int*)malloc(sizeof(int) * N);
if (a5 == NULL)
exit(-1);
int* a6 = (int*)malloc(sizeof(int) * N);
if (a6 == NULL)
exit(-1);
int* a7 = (int*)malloc(sizeof(int) * N);
if (a7 == NULL)
exit(-1);
for (int i = 0; i < N; ++i)
{
a1[i] = rand();
//a1[i] = rand() + i;
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
a6[i] = a1[i];
a7[i] = a1[i];
}
int begin1 = clock();
SInsertSort(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();
MergerSort(a6, N);
int end6 = clock();
int begin7 = clock();
BubbleSort(a7, N);
int end7 = 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("BubbleSort:%d\n", end7 - begin7);
printf("QuickSort:%d\n", end5 - begin5);
printf("MergeSort:%d\n", end6 - begin6);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
free(a7);
}
我们来测试一下：
首先第一次10000个数据： 然后我们会分别获取一下，程序运行开始和结束的时间： 最后相减就能得到运行时间，单位是毫秒： 我们来运行一下： 看这个差别就出来了。
再多一点，来10万个：
这次我等的时间就挺长的： 还是10万个，刚才是debug版本下，我们可以换到release下（会对我们的程序进行优化），会快一点： 再增加一点，release下100万个数据，但是像冒泡和直接插入这些比较慢的我们可以把它先屏蔽掉，否则太慢了： 注意：0的那三个屏蔽掉了 🆗，数据越多它们的差距就越明显了。 500万个： 1000万： 快排敢称为“快速排序”确实还是很快的啊。
8. 排序算法复杂度及稳定性分析
9. 源码展示
快排非递归用到的栈
Stack.h
#pragma once
#include
#include
#include
#include
typedef int STDatatype;
typedef struct Stack
{
STDatatype* a;
int top;
int capacity;
}ST;
//初始化
void StackInit(ST* ps);
//销毁
void StackDestroy(ST* ps);
//元素压栈
void StackPush(ST* ps, STDatatype x);
//元素出栈
void StackPop(ST* ps);
//取栈顶元素
STDatatype StackTop(ST* ps);
//求栈中元素个数
int StackSize(ST* ps);
//判断栈是否为空
bool StackEmpty(ST* ps);
Stack.c
#define _CRT_SECURE_NO_WARNINGS
#include "Stack.h"
//初始化
void StackInit(ST* ps)
{
assert(ps);
ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);
assert(ps->a);
ps->capacity = 4;
ps->top = 0;//初始化为0，表示指向栈顶元素的下一个
}
//销毁
void StackDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
//元素压栈
void StackPush(ST* ps, STDatatype x)
{
assert(ps);
//如果满了，扩容，扩到原来两倍
if (ps->top == ps->capacity)
{
STDatatype* tmp = (STDatatype*)realloc(ps->a, ps->capacity * 2 * sizeof(STDatatype));
assert(tmp);
ps->a = tmp;
ps->capacity *= 2;
}
ps->a[ps->top] = x;
ps->top++;
}
//元素出栈
void StackPop(ST* ps)
{
assert(ps);
//栈为空（ps->top==0），就不能再出栈了。
assert(ps->top > 0);
ps->top--;
}
//取栈顶元素
STDatatype StackTop(ST* ps)
{
assert(ps);
//栈为空（ps->top==0），就不能取栈顶元素了。
assert(ps->top > 0);
return ps->a[ps->top-1];
}
//求栈中元素个数
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
//判断栈是否为空
bool StackEmpty(ST* ps)
{
assert(ps);
//如果ps->top == 0成立，结果为true，表示栈空。
return ps->top == 0;
}
sort.h
#pragma once
#include
#include
#include
#include
#include
//打印数组
void PrintArr(int* arr, int n);
//直接插入排序
void SInsertSort(int* arr, int n);
//希尔排序
void ShellSort(int* arr, int n);
//交换
void swap(int* e1, int* e2);
//向下调整（小堆）
void AdjustDown(int* arr, int size, int parent);
//堆排序（升序）
void HeapSort(int* arr, int n);
//直接选择排序
void SelectSort(int* arr, int n);
//冒泡排序
void BubbleSort(int* arr, int n);
//快速排序（递归）
void QuickSort(int* arr, int begin, int end);
//快速排序（非递归）
void QuickSortNonR(int* arr, int begin, int end);
//归并排序（递归）
void MergerSort(int* arr, int n);
//归并排序（非递归）
void MergerSortNonR(int* arr, int n);
//计数排序
void CountSort(int* arr, int n);
sort.c
#define _CRT_SECURE_NO_WARNINGS
#include "sort.h"
#include "Stack.h"
//打印数组
void PrintArr(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
//直接插入排序
void SInsertSort(int* arr, int len)
{
for (int i = 0; i < len - 1; i++)
{
int end = i;
int tmp = arr[end + 1];
while (end >= 0)
{
if (tmp < arr[end])
{
arr[end + 1] = arr[end];
end--;
}
else
{
break;
}
}
arr[end + 1] = tmp;
}
}
//希尔排序
void ShellSort(int* arr, int len)
{
int gap = len;
// gap > 1 预排序
// gap == 1 最后一次直接插入排序
while (gap > 1)
{
//gap /= 2;
gap = gap / 3 + 1;
for (int i = 0; i < len - gap; i++)
{
int end = i;
int tmp = arr[end + gap];
while (end >= 0)
{
if (tmp < arr[end])
{
arr[end + gap] = arr[end];
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = tmp;
}
}
}
//交换
void swap(int* e1, int* e2)
{
int tmp = *e1;
*e1 = *e2;
*e2 = tmp;
}
//向下调整（大堆）
void AdjustDown(int* arr, int size, int parent)
{
assert(arr);
int child = parent * 2 + 1;
//没有右孩子，说明是个叶子，循环结束
while (child < size)
{
//得出较大的那个孩子，有可能有右孩子，但没有左孩子
//所以加上child + 1 < size
if (child + 1 < size && arr[child + 1] > arr[child])
{
child++;
}
//如果孩子大于父亲，就交换
if (arr[parent] < arr[child])
{
swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
}
//如果小于孩子，调整结束
else
{
break;
}
}
}
//堆排序
void HeapSort(int* arr, int n)
{
//建堆：升序大堆，降序小堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(arr, n, i);
}
int count = n - 1;
while (count > 0)
{
swap(&arr[0], &arr[count]);
AdjustDown(arr, count, 0);
count--;
}
}
//直接选择排序
void SelectSort(int* arr, int n)
{
assert(arr);
int begin = 0;
int end = n - 1;
while (begin < end)
{
int maxi = begin;
int mini = begin;
for (int i = begin+1; i <= end; i++)
{
if (arr[i] > arr[maxi])
{
maxi = i;
}
if (arr[i] < arr[mini])
{
mini = i;
}
}
swap(&arr[mini], &arr[begin]);
if (maxi == begin)
maxi = mini;
swap(&arr[maxi], &arr[end]);
begin++;
end--;
}
}
//冒泡排序
void BubbleSort(int* arr, int n)
{
int i = 0;
for (i = 0; i < n - 1; i++)
{
int j = 0;
int flag = 0;
for (j = 0; j < n - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
swap(&arr[j], &arr[j + 1]);
flag = 1;
}
}
// 一趟冒泡过程中，没有发生交换，说明已经有序了，不需要再处理
if (flag == 0)
break;
}
}
//三数取中
int GetMidIndex(int* arr, int left, int right)
{
//int mid = (left + right) / 2;
//防止left和right太大溢出
int mid = left + (right - left) / 2;
if (arr[mid] > arr[left])
{
if (arr[right] > arr[mid])
return mid;
else if (arr[left] > arr[right])
return left;
else
return right;
}
//arr[mid] < arr[left]
else
{
if (arr[right] < arr[mid])
return mid;
else if (arr[left] > arr[right])
return right;
else
return left;
}
}
//一趟快速排序 [left,right]（hoare版本）
int PartSort(int* arr, int left, int right)
{
int mid = GetMidIndex(arr, left, right);
swap(&arr[mid], &arr[left]);
int keyi = left;
while (left < right)
{
//R先走，向左找小
while (left < right && arr[right] >= arr[keyi])
{
right--;
}
//L向右找大
while (left < right && arr[left] <= arr[keyi])
{
left++;
}
if (left < right)
swap(&arr[left], &arr[right]);
}
int meeti = left;
swap(&arr[meeti], &arr[keyi]);
return meeti;
}
//一趟快速排序 [left,right]（挖坑法）
int PartSort2(int* arr, int left, int right)
{
int mid = GetMidIndex(arr, left, right);
swap(&arr[mid], &arr[left]);
int key = arr[left];
//变量pit标识坑的位置
int pit = left;
while (left < right)
{
//R向左找小于Key的值，填坑
if (left < right && arr[right] >= key)
{
right--;
}
arr[pit] = arr[right];
pit = right;//更新坑
//L向右找大于Key的值，填坑
if (left < right && arr[left] <= key)
{
left++;
}
arr[pit] = arr[left];
pit = left;//更新坑
}
arr[pit] = key;
return pit;
}
//一趟快速排序 [left,right]（前后指针法）
int PartSort3(int* arr, int left, int right)
{
int mid = GetMidIndex(arr, left, right);
swap(&arr[mid], &arr[left]);
int keyi = left;
int prev = keyi;
int cur = keyi + 1;
while (cur <= right)
{
/*if (arr[cur] < arr[keyi])
{
prev++;
swap(&arr[prev], &arr[cur]);
}*/
//或
if (arr[cur] < arr[keyi] && ++prev != cur)
swap(&arr[prev], &arr[cur]);
cur++;
}
swap(&arr[prev], &arr[keyi]);
return prev;
}
//快速排序[begin,end]
void QuickSort(int* arr, int begin, int end)
{
if (begin >= end)
return;
if (end - begin <= 8)
{
// 小区间用直接插入排序，减少递归调用次数
SInsertSort(arr + begin, end - begin + 1);
}
else
{
int keyi = PartSort2(arr, begin, end);
//[begin,keyi-1] keyi [keyi+1,end]
//排keyi左边
QuickSort(arr, begin, keyi - 1);
//排keyi右边
QuickSort(arr, keyi + 1, end);
}
}
//快速排序（非递归）
void QuickSortNonR(int* arr, 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 keyi = PartSort3(arr, left, right);
//[left,keyi-1] keyi [keyi+1,right]
if (right > keyi + 1)
{
StackPush(&st, keyi + 1);
StackPush(&st, right);
}
if (keyi - 1 > left)
{
StackPush(&st, left);
StackPush(&st, keyi - 1);
}
}
StackDestroy(&st);
}
void _MergerSort(int* arr, int begin, int end, int* tmp)
{
if (begin >= end)
return;
int mid = (begin + end) / 2;
//[begin,mid] [mid+1,end]
_MergerSort(arr, begin, mid, tmp);
_MergerSort(arr, mid + 1, end, tmp);
//归并
int begin1 = begin;
int end1 = mid;
int begin2 = mid + 1;
int end2 = end;
int i = begin;
//归并，取小的尾插（升序）
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] <= arr[begin2])
{
tmp[i++] = arr[begin1++];
}
else
{
tmp[i++] = arr[begin2++];
}
}
//循环结束时哪个区间还有剩余数据，就把剩余数据续到后面
while (begin1 <= end1)
{
tmp[i++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = arr[begin2++];
}
//最后把排好数据再拷回原数组（只拷贝当前归并的区间）
memcpy(arr + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
//归并排序（递归）
void MergerSort(int* arr, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
_MergerSort(arr, 0, n - 1, tmp);
free(tmp);
tmp = NULL;
}
//归并排序（非递归）
void MergerSortNonR(int* arr, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
int gap = 1;
while (gap < n)
{
for (int j = 0; j < n; j += 2 * gap)
{
//归并
int begin1 = j;
int end1 = j + gap - 1;
int begin2 = j + gap;
int end2 = j + 2 * gap - 1;
//判断越界的情况并进行处理
//第一组部分越界
if (end1 >= n)
break;
//第二组全部越界
if (begin2 >= n)
break;
//第二组部分越界
if (end2 >= n)
end2 = n - 1;
int i = j;
//归并，取小的尾插（升序）
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] <= arr[begin2])
{
tmp[i++] = arr[begin1++];
}
else
{
tmp[i++] = arr[begin2++];
}
}
//循环结束时哪个区间还有剩余数据，就把剩余数据续到后面
while (begin1 <= end1)
{
tmp[i++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = arr[begin2++];
}
//最后把排好数据再拷回原数组（只拷贝当前归并的区间）
memcpy(arr + j, tmp + j, (end2 - j + 1) * sizeof(int));
}
gap *= 2;
}
free(tmp);
tmp = NULL;
}
//计数排序
void CountSort(int* arr, int n)
{
assert(arr);
//找最值
int max = arr[0];
int min = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] > max)
max = arr[i];
if (arr[i] < min)
min = arr[i];
}
int range = max - min + 1;
//创建数组
/*int* count = (int*)malloc(sizeof(int) * range);
if (count == NULL)
{
perror("malloc fail");
return;
}
memset(count, 0, sizeof(int) * range);*/
int* count = (int*)calloc(range, sizeof(int));
if (count == NULL)
{
perror("malloc fail");
return;
}
//统计个数
for (int i = 0; i < n; i++)
{
count[arr[i] - min]++;
}
//排序(遍历count数组按个数往原数组放数据）
int j = 0;
for (int i = 0; i < range; i++)
{
//count[i]就是每个数据出现的次数
while (count[i]--)
{
arr[j] = i + min;
j++;
}
}
//释放malloc的数组
free(count);
count = NULL;
}
test.c
#define _CRT_SECURE_NO_WARNINGS
#include "sort.h"
#include "Stack.h"
void SInsertSorttest()
{
int arr[] = { 48,62,35,77,55,14,35,98 };
SInsertSort(arr, sizeof(arr) / sizeof(arr[0]));
PrintArr(arr, sizeof(arr) / sizeof(arr[0]));
}
void ShellSorttest()
{
int arr[] = { 9,1,2,5,7,4,8,6,3,5 };
ShellSort(arr, sizeof(arr) / sizeof(arr[0]));
PrintArr(arr, sizeof(arr) / sizeof(arr[0]));
}
void HeapSorttest()
{
int arr[] = { 9,1,2,5,7,4,8,6,3,5 };
//int arr[] = { 1,1,1,1,1,1,1,1,1,1 };
HeapSort(arr, sizeof(arr) / sizeof(arr[0]));
PrintArr(arr, sizeof(arr) / sizeof(arr[0]));
}
void SelectSorttest()
{
//int arr[] = { 34,56,25,65,86,99,72,66 };
int arr[] = { 9,1,2,5,7,4,8,6,3,5 };
SelectSort(arr, sizeof(arr) / sizeof(arr[0]));
PrintArr(arr, sizeof(arr) / sizeof(arr[0]));
}
void BubbleSorttest()
{
int arr[] = { 9,1,2,5,7,4,8,6,3,5 };
BubbleSort(arr, sizeof(arr) / sizeof(arr[0]));
PrintArr(arr, sizeof(arr) / sizeof(arr[0]));
}
void QuickSorttest()
{
int arr[] = { 9,1,2,5,7,4,8,6,3,5 };
QuickSort(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1);
//QuickSortNonR(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1);
PrintArr(arr, sizeof(arr) / sizeof(arr[0]));
}
void MergerSorttest()
{
//int arr[] = { 9,1,2,5,7,4,8,6,3,5 };
int arr[] = { 10,6,7,1,3,9,4,2,5 ,11,-1};
//MergerSort(arr, sizeof(arr) / sizeof(arr[0]));
MergerSortNonR(arr, sizeof(arr) / sizeof(arr[0]));
PrintArr(arr, sizeof(arr) / sizeof(arr[0]));
}
void CountSorttest()
{
//int arr[] = { 10,6,7,1,3,9,4,2,5 ,11, };
int arr[] = { -5, 4, 3, -3, -5, -3, -3, 2, 3, 4, 3, 2 };
CountSort(arr, sizeof(arr) / sizeof(arr[0]));
PrintArr(arr, sizeof(arr) / sizeof(arr[0]));
}
void TestOP()
{
srand(time(0));
const int N = 1000000;
int* a1 = (int*)malloc(sizeof(int) * N);
if (a1 == NULL)
exit(-1);
int* a2 = (int*)malloc(sizeof(int) * N);
if (a2 == NULL)
exit(-1);
int* a3 = (int*)malloc(sizeof(int) * N);
if (a3 == NULL)
exit(-1);
int* a4 = (int*)malloc(sizeof(int) * N);
if (a4 == NULL)
exit(-1);
int* a5 = (int*)malloc(sizeof(int) * N);
if (a5 == NULL)
exit(-1);
int* a6 = (int*)malloc(sizeof(int) * N);
if (a6 == NULL)
exit(-1);
int* a7 = (int*)malloc(sizeof(int) * N);
if (a7 == NULL)
exit(-1);
for (int i = 0; i < N; ++i)
{
a1[i] = rand();
//a1[i] = rand() + i;
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
a6[i] = a1[i];
a7[i] = a1[i];
}
int begin1 = clock();
//SInsertSort(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();
MergerSort(a6, N);
int end6 = clock();
int begin7 = clock();
//BubbleSort(a7, N);
int end7 = clock();
printf("SInsertSort:%d\n", end1 - begin1);
printf("ShellSort:%d\n", end2 - begin2);
printf("SelectSort:%d\n", end3 - begin3);
printf("HeapSort:%d\n", end4 - begin4);
printf("BubbleSort:%d\n", end7 - begin7);
printf("QuickSort:%d\n", end5 - begin5);
printf("MergerSort:%d\n", end6 - begin6);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
free(a7);
}
int main()
{
//SInsertSorttest();
//ShellSorttest();
HeapSorttest();
//SelectSorttest();
//BubbleSorttest();
//QuickSorttest();
//MergerSorttest();
//CountSorttest();
//TestOP();
return 0;
}
以上就是对一些常见排序算法的讲解，欢迎大家指正！！！