目录
1.堆排序
2.快速排序
1.hoare版本
2.挖坑法
3.前后指针法
4.非递归实现快排
注意点
3.归并排序
1.递归版本
2.非递归版本
1.堆排序
void Swap(int* a, int* b) { int tmp = *a; *a = *b; *b = tmp; } void adjustdown(int* a, int n, int parent) { int child = parent * 2 + 1; while (child < n) { if (child + 1 < n && a[child + 1] > a[child]) { child++; } if (a[parent] < a[child]) { Swap(&a[parent], &a[child]); } else { break; } parent = child; child = parent * 2 + 1; } } void heapsort(int* a, int n) { for (int i = (n - 1 -1) / 2; i >= 0; i--) { adjustdown(a, n, i); } for (int i = n-1; i > 0; i--) { Swap(&a[0], &a[i]); adjustdown(a, i, 0); } } void printarr(int* a, int n) { for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } void heaptest() { int arr[] = { 4,7,1,9,3,6,5,8,3,2,0 }; printarr(arr, sizeof(arr)/sizeof(int)); heapsort(arr, sizeof(arr)/sizeof(int)); printarr(arr, sizeof(arr)/sizeof(int)); }我们先用向下调整算法建堆。
使用向下调整算法建堆的前提是，该节点的子树都是堆。那么我们从最后一个节点的父节点开始向下调整算法，这样因为两个子树都是叶子节点，因此满足条件。从后往前，一直遍历到父节点为根节点，那么就建好堆了。
然后只需要不断将第一个和最后一个节点的值交换，把最大值放到末尾，然后不断从根节点向下建堆，即可每次都挑选出最大值，我们依次把他们放到末尾即可。
2.快速排序
主逻辑，递归
1.hoare版本
void Swap(int* a, int* b) { int tmp = *a; *a = *b; *b = tmp; } void printarr(int* a, int n) { for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } int partsort(int* a, int left, int right) { int keyi = left; while (left < right) { while (left < right &&a[left] <= a[keyi]) { left++; } while (left < right && a[right] >= a[keyi]) { right--; } Swap(&a[left], &a[right]);//如果是因为left==right结束，交换值也并不影响结果 } Swap(&a[keyi], &a[left]); return left; } void quicksort(int* a, int begin, int end) { if (begin >= end)return; int keyi = partsort(a, begin, end); quicksort(a, begin, keyi-1); quicksort(a, keyi + 1, end); } void quicktest() { int arr[] = { 4,7,1,9,3,6,5,8,3,2,0 }; printarr(arr, sizeof(arr) / sizeof(int)); quicksort(arr,0, sizeof(arr) / sizeof(int)-1); printarr(arr, sizeof(arr) / sizeof(int)); }我们以左边第一个下标为keyi，因此先从右边开始找
1.先从右往左找到比a【keyi】小的值
2.再从左往右找到比a【keyi】大的值
交换这两个值。
3.不断重复以上过程直到相遇left == right
4.交换a【keyi】和a【left】
注意点
1.我们在移动下标时，判断条件是a[left] <= a[keyi]left++
a[right] >= a[keyi] right--
这是为了防止遇到与a【keyi】相等的值的时候，陷入死循环
2.我们在寻找下标的小循环中也加入left<right的判断是因为防止极端情况。
如果不判断就会越界，而且如果是因为left==right结束，交换值也并不影响结果
同时因为这个极端情况原因，我们遍历是从最左边keyi处开始遍历，不然会忽略掉这种情况。也是注意点1中判断条件需要加=的原因
3.我们再来谈谈为什么从一边开始调整要从另一边开始找起
以上面的情况为例子，
因为这样可以保证他们相遇时候所处在的值一定比a【keyi】小
情况1、left不动，right先移动与left相遇，此时a【keyi】还在原位
情况2. right移动后找到小值，left移动后与right相遇，此时该位置的值比a【keyi】小
情况3，left与right先各自移动并且交换一次，然后right再移动和left相遇，此时因为已经交换过，a【left】处储存的值小于a【keyi】因此也符合
综上
2.挖坑法
int partsort(int* a, int left, int right) { int key = a[left]; while (left < right) { while (left < right && a[right] >= key) { right--; } a[left] = a[right]; while (left < right && a[left] <= key) { left++; } a[right] = a[left]; } a[left] = key; return left; }把a【keyi】的位置先挖走，记录这个key值。
1.从右边往左找小，把这个值填入坑中，同时这个位置形成一个新的坑
2.从左边往右找大 把这个值填入坑中，同时这个位置形成一个新的坑
3.重复以上操作，直到left==right，然后把key值填入这个坑中，此时这个位置一定是坑，因为left和right永远有一个是坑
3.前后指针法
int partsort(int* a, int left, int right) { int prev = left; int cur = left + 1; int keyi = left; while (cur <= right) { if (a[cur] < a[keyi] && ++prev != cur)//这里直接判断一下，相等就不交换，并且在判断条件 //的地方就更新prev { Swap(&a[prev], &a[cur]); } ++cur;//cur就是一直往前走，直到结束，遇到相应位置才有操作，因此直接放到循环中 } Swap(&a[keyi], &a[prev]); keyi = prev; return keyi; }cur一直向后找小于key的位置
如果a【cur】< key
++prev，然后交换a【prev】和a【cur】
如果cur所在位置的值都比key小，那么cur和prev拉不开差距.++prev后和cur交换就是自身交换
如果遇到比key大的值，就会拉开差距，此时如果cur遇到比key小的值，这个值就会和一个比key大的值交换，因为prev和cur原本中间隔着的都是大于key的值，++prev后再交换就会是这样的结果
这样相当于把大的往右推，小的往左推
cur走出数组结束，key与a【prev】交换即可
4.非递归实现快排
stack.h
#pragma once #include <malloc.h> #include <stdio.h> #include <cassert> #define INITSIZE 20 // 支持动态增长的栈 typedef int STDataType; typedef struct Stack { STDataType* _a; int _top; // 栈顶 int _capacity; // 容量 }Stack; // 初始化栈 void StackInit(Stack* ps); // 入栈 void StackPush(Stack* ps, STDataType data); // 出栈 void StackPop(Stack* ps); // 获取栈顶元素 STDataType StackTop(Stack* ps); // 获取栈中有效元素个数 int StackSize(Stack* ps); // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 int StackEmpty(Stack* ps); // 销毁栈 void StackDestroy(Stack* ps);stack.cpp
#define _CRT_SECURE_NO_WARNINGS 1 #include"stack.h" void CheckCapacity(Stack* ps) { if (ps->_top + 1 < ps->_capacity) return; STDataType* tmp = (STDataType*)realloc(ps->_a, ps->_capacity * 2 * sizeof(STDataType)); if (tmp == NULL) { perror("CheckCapacity"); return; } ps->_a = tmp; ps->_capacity = ps->_capacity * 2; } // 初始化栈 void StackInit(Stack* ps) { STDataType* tmp = (STDataType*)malloc(INITSIZE * sizeof(STDataType)); if (tmp == NULL) { perror("StackInit"); return; } ps->_a = tmp; ps->_capacity = INITSIZE; ps->_top = -1; } // 入栈 void StackPush(Stack* ps, STDataType data) { CheckCapacity(ps); ps->_top++; ps->_a[ps->_top] = data; } // 出栈 void StackPop(Stack* ps) { if (ps->_top == -1)return; ps->_top--; } // 获取栈顶元素 STDataType StackTop(Stack* ps) { assert(!StackEmpty(ps)); return ps->_a[ps->_top]; } // 获取栈中有效元素个数 int StackSize(Stack* ps) { return ps->_top + 1; } // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 int StackEmpty(Stack* ps) { if (ps->_top == -1)return 1; return 0; } // 销毁栈 void StackDestroy(Stack* ps) { assert(ps); free(ps->_a); ps->_a = NULL; ps->_capacity = 0; ps->_top = -1; }void QuickSortNonR(int* a, int begin, int end)//非递归快排 用栈模拟递归过程 { Stack st; StackInit(&st); StackPush(&st, end);//我们需要一个区间，这里直接让两个数入栈，只是顺序需要注意 StackPush(&st, begin);//因为栈是先进后出 因此先进end int left, right, keyi; while (!StackEmpty(&st)) { left = StackTop(&st); StackPop(&st); right = StackTop(&st); StackPop(&st); keyi = PartSort(a, left, right);//由于栈后进先出的性质，我们每次先把右半部分入栈 if (keyi + 1 < right) { StackPush(&st, right); StackPush(&st, keyi + 1); } if (keyi - 1 > left) { StackPush(&st, keyi - 1); StackPush(&st, left); } } StackDestroy(&st); }注意点
以上三种方法只是实现形式不同，时间复杂度是完全相同的，并且主逻辑的代码不需要更改，就是一个递归，只需要把部分排序修改即可
3.归并排序
将已有序的子序列合并，得到完全有序的序列。
下图可以形象说明其过程，不断向下分解，知道每个子区间都有序，将两个子区间合并，不断重复即可得到最终的结果。
1.递归版本
void _MergeSort(int* a, int begin, int end, int* tmp) { if (begin >= end)return; if (end - begin + 1< 10)//小区间优化 区间很小的时候就不继续递归，而是采用一种相对效率较高的排序。因为递归时最下面的几层要进行的调用是最多的 { InsertSort(a + begin, end - begin + 1); return; } int mid = begin + (end - begin) / 2; _MergeSort(a, begin, mid, tmp); _MergeSort(a, mid + 1, end, tmp); int left = begin; int right = mid + 1; int n = begin; while (left <= mid && right <= end) { if (a[left] <= a[right]) { tmp[n++] = a[left++]; } else { tmp[n++] = a[right++]; } } while (left <= mid) { tmp[n++] = a[left++]; } while (right <= end) { tmp[n++] = a[right++]; } for (int i = begin; i <= end; i++) { a[i] = tmp[i]; } } void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); _MergeSort(a, 0, n - 1 , tmp); free(tmp); }小区间优化，优化后排序效率会增高一些，但是是锦上添花，并没有产生质变
2.非递归版本
思路其实很简单，就是每组一个进行排序，然后每组两个，四个，八个进行排序，使用循环即可
void MergeSortNonR(int* a, int n) { int gap = 1; int* tmp = (int*)malloc(sizeof(int) * (n + 1)); while (gap <= n) { int begin1, end1, begin2, end2; for (begin1 = 0; begin1 <= n; begin1 += gap * 2) { end1 = begin1 + gap - 1; begin2 = begin1 + gap; end2 = begin1 + gap * 2 - 1; if (end1 > n || begin2 > n)break; if (end2 > n)end2 = n; int left = begin1; int right = begin2; int index = begin1; while (left <= end1 && right <= end2) { if (a[left] <= a[right]) { tmp[index++] = a[left++]; } else { tmp[index++] = a[right++]; } } while (left <= end1) { tmp[index++] = a[left++]; } while (right <= end2) { tmp[index++] = a[right++]; } for (int i = begin1; i <= end2; i++)//排一段赋一段 越界就break { a[i] = tmp[i]; } } gap *= 2; } } void MergeSortNonR2(int* a, int n)//这个2只是换一种方式处理边界问题 { int gap = 1; int* tmp = (int*)malloc(sizeof(int) * (n + 1)); while (gap <= n) { int begin1, end1, begin2, end2; for (begin1 = 0; begin1 <= n; begin1 += gap * 2) { end1 = begin1 + gap - 1; begin2 = begin1 + gap; end2 = begin1 + gap * 2 - 1; if (end1 > n) { end1 = n - 1; begin2 = n; end2 = n - 1; } else if (begin2 > n) { begin2 = n; end2 = n - 1; } else if (end2 > n) { end2 = n; } int left = begin1; int right = begin2; int index = begin1; while (left <= end1 && right <= end2) { if (a[left] <= a[right]) { tmp[index++] = a[left++]; } else { tmp[index++] = a[right++]; } } while (left <= end1) { tmp[index++] = a[left++]; } while (right <= end2) { tmp[index++] = a[right++]; } } for (int i = 0; i <= n; i++)//一次性都排好，越界修改边界，如果边界失效，就让begin > end,这样数组a就不会把它的值赋给tmp了 { a[i] = tmp[i]; } gap *= 2; } }4.计数排序
时间复杂度（N + range）
空间复杂度（range）
在某些情况下，计数排序其实是效率非常高的一种排序
但是它有两个比较大的弊端
第一即它依赖数据范围，适用于范围集中的数组
第二即它依赖下标对应，即它只能排序整型
void CountSort(int* a, int n) { int min = a[0]; int max = a[0]; for (int i = 0; i < n; i++) { if (a[i] < min) min = a[i]; if (a[i] > max) { max = a[i]; } } int range = max - min + 1; int* tmp = (int*)malloc(sizeof(int) * range); memset(tmp, 0, sizeof(int) * range); for (int i = 0; i < n; i++) { tmp[a[i] - min]++; } int count = 0; for (int i = 0; i < range; i++) { while(tmp[i] > 0) { a[count++] = i + min; tmp[i]--; } } }5.稳定性
稳定性简而言之，可以用一下例子简单介绍
稳定性一般用于以某种标准确定某些相同数的排序
比如比赛时相同分数时时间花费少的排名考前
又或者例如考试成绩同分时按语文成绩排序，我们可以先将名次按照语文成绩排序，再按照总分排序，这样即可顺利划分
下面是一些常见排序的稳定性
比较值得注意的是选择排序，选择排序可以在选数的时候保证稳定性，但是在交换数据的时候就不能保证了
