本文章承接上篇文章的交换排序继续
本文与上文的完整代码放在文章末尾处
目录
一、快速排序
基本思想
1.hoare版本
思路：
A、递归，二叉树结构的排序
编辑
a、代码
2.快排挖坑法
思路：
代码：
3.前后指针快排
思路：
代码：
4.为什么相遇位置比key小？
B、非递归，使用栈模拟递归
思路：利用栈来存数组下标，一定要注意存下标的顺序：栈（先进后出，后进先出）
代码：
C、快速排序的特性总结
二、归并排序
基本思想：
A、递归
思路：
代码：
B、非递归
思路：
代码：
三、完整代码：
Sort.h
Sort.c
Test.c
一、快速排序
基本思想
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
1.hoare版本
思路：
right右先动，找比a[key]小的值，找到后不动，left左动，找比a[key]大的值，找到后交换left，right的值。直到right,left相遇，再将a[key]的值与left的值交换。此时key的值已固定，左边比它小，右边比他大。
如图：一趟排序
多趟排序，我们用到类似于二叉树的方式：
A、递归，二叉树结构的排序
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
//int key = HoareSort(a, begin, end);
//int key = DigSort(a, begin, end);int key = PTSort(a, begin, end);
QuickSort(a, begin, key - 1);
QuickSort(a, key + 1, end);
}
a、代码
int HoareSort(int* a, int begin, int end)
{
int midi = Getmid(a, begin, end);
Swap(&a[midi], &a[begin]);
int left = begin, right = end;//注意1：left一定从头开始
int key = begin;
while (left < right)
{
while (left < right && a[right] >= a[key])//注意2：一定是a[right] >= a[key]而不是
//a[right] > a[key](相等的值跳过)
{
--right;
}
while (left < right && a[left] <= a[key])
{
++left;
}
Swap(&a[left], &a[right]); }//将所有的值都换完后，再将left的值与key值相换，key与right相遇的位置的值是比key值小的
Swap(&a[key], &a[left]);
key = left;//再将key置为他现在所在的位置
return key;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
//int key = HoareSort(a, begin, end);QuickSort(a, begin, key - 1);
QuickSort(a, key + 1, end);
}
b.快速排序优化（a.三数取中法选key b.递归到小的子区间时，可以考虑使用插入排序（省略））
2.快排挖坑法
思路：
先将第一个数据存放在临时变量key中，形成一个坑位，right右边先找小，找到比key小的放入坑中，此时right位置成为新的坑位，left左边找大，将大的数据放入这个新坑中，直到left与right相遇，将key的值放入此时的坑中。
代码：
int DigSort(int* a, int begin, int end)
{int midi = Getmid(a, begin, end);Swap(&a[midi], &a[begin]);int keyval = a[begin];int hole = begin;while (begin < end){while (begin < end && a[end] >= keyval){--end;}a[hole] = a[end];hole = end;while (begin < end && a[begin] <= keyval){++begin;}a[hole] = a[begin];hole = begin;}a[hole] = keyval;return hole;
}
void QuickSort(int* a, int begin, int end)
{if (begin >= end){return;}
void QuickSort(int* a, int begin, int end)
{if (begin >= end){return;}//int key = HoareSort(a, begin, end);int key = DigSort(a, begin, end);QuickSort(a, begin, key - 1);QuickSort(a, key + 1, end);
}
void QuickSort(int* a, int begin, int end)
{if (begin >= end){return;}//int key = HoareSort(a, begin, end);int key = DigSort(a, begin, end);QuickSort(a, begin, key - 1);QuickSort(a, key + 1, end);
}QuickSort(a, begin, key - 1);QuickSort(a, key + 1, end);
}3.前后指针快排
思路：
初始时，prev指针指向序列开头，cur指针指向prev指针的后一个位置
相当于把小的值全留在左边。
1.cur 遇到比key大的值，++cur
2.cur 遇到比key小的值，++prev,交换prev和cur的值
代码：
int PTSort(int* a, int begin, int end)
{
int midi = Getmid(a, begin, end);
Swap(&a[midi], &a[begin]);
int key = begin;
int prev = begin;
int cur = begin + 1;
while (cur <= end)
{
if (a[cur] < a[key] && ++prev != cur)
{
Swap(&a[cur], &a[prev]);
}++cur;
}
Swap(&a[prev], &a[key]);
key = prev;
return key;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
//int key = HoareSort(a, begin, end);
//int key = DigSort(a, begin, end);int key = PTSort(a, begin, end);
QuickSort(a, begin, key - 1);
QuickSort(a, key + 1, end);
}
4.为什么相遇位置比key小？
B、非递归，使用栈模拟递归
思路：利用栈来存数组下标，一定要注意存下标的顺序：栈（先进后出，后进先出）
栈的具体讲解见：栈的讲解与实现
代码：
void QuickSortNonR(int* a, int begin, int end)
{
Stack s;
StackInit(&s);
StackPush(&s, end);
StackPush(&s, begin);
while (!StackEmpty(&s))
{
int left = StackTop(&s);
StackPop(&s);
int right = StackTop(&s);
StackPop(&s);
int key = PTSort(a,left,right)
; if (left < key - 1)
{
StackPush(&s, key - 1);
StackPush(&s, left);}
if (right > key + 1)
{
StackPush(&s, right);
StackPush(&s, key + 1);
}}
StackDestroy(&s);
}
C、快速排序的特性总结
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定
二、归并排序
基本思想：
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
A、递归
思路：
如果有两个近似有序的数组，想要将他们组成一个有序数组，分别依次取两个数组的第一个值到最后一个值进行比较，取最小的尾插进新数组
而归并排序怎么玩呢？实际上排序前，我们的数组不是上面已经有序的两个数组，因此我们还需要将我们的数组变得“有序”
我们现将数组拆分，拆分到最后，每组只剩一个值，一个值就是一个有序的数组，再将这一个值如
前面的图一般，找小值再进行尾插。
代码：
void _MergeSort(int* a, int begin, int end, int* tmp)
{
if (begin >= end)
return;int mid = (begin + end) / 2;
//[begin, mid][mid+1, end]
_MergeSort(a, begin, mid, tmp);
_MergeSort(a, mid + 1, end, tmp);// [begin, mid][mid+1, end]归并
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int i = begin;
while (begin1 <= end1 && begin2 <= end2)
{
if ( a[begin1] < a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}}
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}void MergeSort(int* a, int n )
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}_MergeSort(a, 0 ,n-1 ,tmp);
free(tmp);
}
B、非递归
思路：
用gap来使用每组的数据个数从1递增，每次都需是2的倍数，因为每次相当于两个数组在进行比较，将值尾插到新数组中，gap每换一次前，都需要将在新数组中的值拷贝回原数组中，用于下一次的排序。
代码：
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
int gap = 1;while (gap < n)
{
for (size_t i = 0; i < n; i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;为了防止下面情况的发生：
if (end1 >= n || begin2 >= n)
{
break;
}if (end2 >= n)
{
end2 = n - 1;
}int j = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[j++] = a[begin1++];
}
else
{
tmp[j++] = a[begin2++];
}}
while (begin1 <= end1)
{
tmp[j++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[j++] = a[begin2++];
}
memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
}
gap *= 2;
}
free(tmp);
}
C、归并排序的特性总结：
1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定
三、完整代码：
Sort.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
#include<time.h>void PrintArray(int* a, int n);
void InsertSort(int* a, int n);
void BubbleSort(int* a, int n);
void ShellSort(int* a, int n);
void SelectSort(int* a, int n);void HeapSort(int* a, int n);
//
void QuickSort(int* a, int begin, int end);
void QuickSortNonR(int* a, int begin, int end);
void MergeSort(int* a, int n);
void MergeSortNonR(int* a, int n);
Sort.c
#include"Sort.h"
#include"Stact.h"
void PrintArray(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}
void InsertSort(int* a, int n)//升序
{for (int i = 0; i < n - 1; i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}
}
void Swap(int* t1,int* t2)
{int tmp = *t1;*t1 = *t2;*t2 = tmp;
}
void BubbleSort(int* a, int n)
{for (int j = 0; j < n; j++){for (int i = 1; i < n-j; i++){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);}}}
}void ShellSort0(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;for (int j = 0; j < gap; ++j){for (int i = j; i < n - gap; i += gap){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}}
}void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}void SelectSort(int* a, int n)
{int begin = 0;int end = n - 1;while(begin < end){int mini = begin, maxi = begin;for (int i = begin + 1; i <= end; i++){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[begin], &a[mini]);if (maxi == begin){maxi = mini;}Swap(&a[end], &a[maxi]);--end;begin++;}
}void AdjustDown(int* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size){if (child + 1 < size && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}// 升序
void HeapSort(int* a, int n)
{for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}
int Getmid(int* a, int begin, int end)
{int midi = (begin + end) / 2;if (a[begin] > a[end]){if (a[end] > a[midi]){return end;}else if(a[begin]<a[midi]){return begin;}else{return midi;}}else{if (a[begin] < a[midi]){return begin;}else if (a[end] > a[midi]){return end;}else{return midi;}}
}int HoareSort(int* a, int begin, int end)
{int midi = Getmid(a, begin, end);Swap(&a[midi], &a[begin]);int left = begin, right = end;int key = begin;while (left < right){while (left < right && a[right] >= a[key]){--right;}while (left < right && a[left] <= a[key]){++left;}Swap(&a[left], &a[right]);}//将所有的值都换完后，再将left的值与key值相换，key与right相遇的位置的值是比key值小的Swap(&a[key], &a[left]);key = left;//再将key置为他现在所在的位置return key;
}
int DigSort(int* a, int begin, int end)
{int midi = Getmid(a, begin, end);Swap(&a[midi], &a[begin]);int keyval = a[begin];int hole = begin;while (begin < end){while (begin < end && a[end] >= keyval){--end;}a[hole] = a[end];hole = end;while (begin < end && a[begin] <= keyval){++begin;}a[hole] = a[begin];hole = begin;}a[hole] = keyval;return hole;
}int PTSort(int* a, int begin, int end)
{int midi = Getmid(a, begin, end);Swap(&a[midi], &a[begin]);int key = begin;int prev = begin;int cur = begin + 1;while (cur <= end){if (a[cur] < a[key] && ++prev != cur){Swap(&a[cur], &a[prev]);}++cur;}Swap(&a[prev], &a[key]);key = prev;return key;
}//
void QuickSort(int* a, int begin, int end)
{if (begin >= end){return;}//int key = HoareSort(a, begin, end);//int key = DigSort(a, begin, end);int key = PTSort(a, begin, end);QuickSort(a, begin, key - 1);QuickSort(a, key + 1, end);
}void QuickSortNonR(int* a, int begin, int end)
{Stack s;StackInit(&s);StackPush(&s, end);StackPush(&s, begin);while (!StackEmpty(&s)){int left = StackTop(&s);StackPop(&s);int right = StackTop(&s);StackPop(&s);int key = PTSort(a,left,right)
; if (left < key - 1){StackPush(&s, key - 1);StackPush(&s, left);}if (right > key + 1){StackPush(&s, right);StackPush(&s, key + 1);}}StackDestroy(&s);
}void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin >= end)return;int mid = (begin + end) / 2;_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid + 1, end, tmp);int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if ( a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}void MergeSort(int* a, int n )
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}_MergeSort(a, 0 ,n-1 ,tmp);free(tmp);
}void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1;while (gap < n){for (size_t i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;if (end1 >= n || begin2 >= n){break;}if (end2 >= n){end2 = n - 1;}int j = begin1;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}gap *= 2;}free(tmp);}Test.c
#include"Sort.h"void TestInsertSort()
{int a[] = { 3, 2, 6, 8, 4, 6, 0, 9, 5, 7, 1 };InsertSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}
//
void TestBubbleSort()
{int a[] = { 3, 2, 6, 8, 4, 6, 0, 9, 5, 7, 1 };BubbleSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}void TestShellSort()
{int a[] = { 3, 2, 6, 8, 4, 6, 0, 9, 5, 7, 1 };ShellSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}
void TestSelectSort()
{//int a[] = { 3, 2, 6, 8, 4, 6, 0, 9, 5, 7, 1 };int a[] = { 13, 2, 6, 8, 4, 6, 0, 9, 5, 7, 1 };SelectSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}void TestHeapSort()
{//int a[] = { 3, 2, 6, 8, 4, 6, 0, 9, 5, 7, 1 };int a[] = { 13, 2, 6, 8, 4, 6, 0, 9, 5, 7, 1 };HeapSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}
//
void TestQuickSort()
{//int a[] = { 3, 2, 6, 8, 4, 6, 0, 9, 5, 7, 1 };//int a[] = {6,1,2,7,9,3,4,5,10,8};int a[] = { 6,1,2,6,7,9,3,4,6,10,8 };PrintArray(a, sizeof(a) / sizeof(int));//QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);QuickSortNonR(a, 0, sizeof(a) / sizeof(int) - 1);PrintArray(a, sizeof(a) / sizeof(int));}void TestMergeSort()
{//int a[] = { 3, 2, 6, 8, 4, 6, 0, 9, 5, 7, 1 };//int a[] = {6,1,2,7,9,3,4,5,10,8};int a[] = { 6,1,2,6,7,9,3,4,6,10,8 };PrintArray(a, sizeof(a) / sizeof(int));//MergeSort(a, sizeof(a) / sizeof(int));MergeSortNonR(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}//测试排序的性能对比
void TestOP()
{srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);int* a6 = (int*)malloc(sizeof(int) * N);int* a7 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();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();InsertSort(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();//MergeSort(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("QuickSort:%d\n", end5 - begin5);printf("MergeSort:%d\n", end6 - begin6);printf("BubbleSort:%d\n", end7 - begin7);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);
}
int main()
{//TestInsertSort();//TestBubbleSort();TestShellSort();//TestSelectSort();//TestHeapSort();//TestQuickSort();//TestMergeSort();//TestOP();return 0;
}