- 九大排序
- 冒泡排序
- 选择排序
- 插入排序
- 希尔排序
- 归并排序
- 快速排序
- 快速排序版本1：挖坑法
- 快排优化版本(三数取中and小区间优化)
- 快速排序版本2：左右指针法
- 快速排序版本3：前后指针法
- 非递归借助栈实现递归
- 计数排序
- 基数排序
- 堆排序
算法思想，进行n-1趟外循环，也即是第一次将数组的最大值移动到数组尾部，第二次就是第二大，，，进行n-1次循环是因为每次一个最后进行n-1次之后最后一个元素的位置也就固定了。内循环就是比较两个元素的大小，将大的元素放到小元素的后面，每次循环之后比较的元素就减去一个，因为循环完一次就有一个数组最大值移动到了数组的尾部。
加入标志位flag，如果某次循环没有数组元素交换，那么这个数组就已经是有序了
#include选择排序int main() { //冒泡排序 int arr[10] = { 32,5,66,77,7,4,97,4,3,0 }; int flag = 0; for (int i = 1; i < 10; i++) { flag = 0; for (int j = 0; j < 10 - i; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j+1]; arr[j + 1] = tmp; flag = 1; } } if (flag == 0) { break; } } return 0; }
算法思想：每次在数组中选择一个最小值，将最小值与数组第一个元素交换，然后再找出数组第二个到最后的元素中的最小值，将他放在数组第二个元素的位置。
我写的时优化版本：思想时选择排序的思想，不一样的是，每次选出来两个值，一个最大值一个最小值。然后分别和开始位置和结束位置交换。要注意一个问题，当最大值下标和begin重合时，此时交换mini位置的值和begin位置的值，maxi的值会被交换到mini指向的位置，所以此时要特殊判断。
//选择排序
void SelectSort(int* arr, int sz)
{
int begin = 0;
int end = sz - 1;
int mini = 0;
int maxi = 0;
while (begin <= end)
{
mini = begin;//记得每次交换完要更新mini和maxi
maxi = begin;
for (int i = begin; i <= end; i++)
{
if (arr[i] < arr[mini])
{
mini = i;
}
if (arr[i] > arr[maxi])
{
maxi = i;
}
}
Swap(&arr[begin], &arr[mini]);
if (maxi == begin)
{
maxi = mini;//特殊判断。
}
Swap(&arr[end], &arr[maxi]);
begin++;
end--;
}
}
插入排序
算法思想：设置一个end，代表0————end之间的数都是有序的，然后用end+1位置的数字不断插入，直到最后end是n-2，把end+1，也即是n-1位置的数字插入，最后一个位置的数字插入就完成了排序。
时间复杂度是O（N^2）
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 && a[end] > tmp)
{
a[end + 1] = a[end];
end--;
}
a[end + 1] = tmp;
}
}
希尔排序
算法思想：实际上就是将数组元素分组，例如 n = 10个元素，分为 n/2 组两个同组元素的间隔设为gap = n/2,用数组下标来解释，十个元素分组，将arr[0] arr[5]分为一组，arr[1] arr[6] 分为一组，明白了分组之后，每次将分组后的元素进行插入排序，然后将gap/2在次进行分组，第一次gap为5，第二次就是2，第三次就是1，当gap等于1的时候就相当于对数组进行上个算法，插入排序。
算法设计思想：先将数组进行预排序，也就是gap>1的都是预排序，预排序会让数组接近有序，减少移动次数，可以让大的元素更快的移动到数组尾部，小元素更快的移动到数组前面，因为步长大嘛，这样就可以再最后一次gap==1的时候也即是直接插入排序的排序中，大大减少移动次数。
时间复杂度计算，最外层gap每次除2，相当于每次二分，时间复杂度为O（logN），内层，gap较大时，差不多是O（N）因为移动次数少，gap较小时也是差不多为O（N），因为数组更接近有序，移动次数也少了。
所以总的时间复杂度就是O（N*logN），文献上说平均复杂度是O（1.3N）我也不清楚是怎么算的。
//希尔排序
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap /= 2;
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0 && a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
a[end + gap] = tmp;
}
}
}
归并排序
算法思想:实际使用的就是分治思想，我想要假设八个数组元素有序，只需要分成两组四个元素的数组，这两组都有序，归并起来就是整体有序，想要四个元素有序怎么办呢？继续分治呗，分成两个元素的数组，两个元素怎么有序？再次分，分成一个元素，一个元素就是有序的，归并起来就可以了，总体就是先分后归。
分治思想：就是要求一个大问题，先将他分成小问题，小问题再分成小小问题，直到不可再分割，最后再将小问题合并即可。
*这里的归并有点类似二叉树的后序遍历，先将数组分为左右区间，左区间有序，右区间，有序，就归并，左右区间类似二叉树的左右子树
//归并排序
void _MergeSort(int* a, int left, int right, int* tmp)
{
if (left >= right)
return;
//左区间有序，右区间有序，然后归并就整体有序了。
int mid = (left + right) >> 1;
_MergeSort(a, left, mid, tmp);
_MergeSort(a, mid + 1, right, tmp);
//左右都有序，归并
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = left;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
//拷贝回去
for (int i = left; i <= right; 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);
}
快速排序
快速排序版本1：挖坑法
排序思想：先确定一个关键字key（一般选第一个或者最后一个），然后以该位置为坑，然后通过左右指针开始遍历数组，先在右边找到小于key的值，放到坑里面，然后right变为新的坑，再去左边，找一个大于key的值，放到坑里面，然后left变为新的坑，直到最后left==right跳出循环，这时候再将key放到pivot位置，该位置就是key的最终位置，然后使用分治思想，如果pivot左边时有序的，右边也是有序的那么数组就有序了，所以递归左区间，递归右区间，完成排序。
快速排序类似，二叉树的前序遍历，先解决根，再解决左右子区间（子树）
void QuickSort(int* arr, int begin, int end)
{
if (begin >= end)
return;
int left = begin;
int right = end;
int key = arr[begin];
int pivot = begin;
while(left < right)
{
while(begin< right && arr[right] >= key)
{
--right;
}
arr[pivot] = arr[right];
pivot = right;
while(left < right && arr[begin] <= key)
{
++left;
}
arr[pivot] = arr[left];
pivot = left;
}
arr[pivot] = key;
QuickSort(arr, begin, pivot - 1);
QuickSort(arr, pivot + 1, end);
}
快排优化版本(三数取中and小区间优化)
因为我们知道上述快排在极限情况下，比如数组是有序的，每次选取，选左区间就会遍历右区间，这样快速排序的二分就失效了，所以这时候时间复杂度是O（N^2),这时候我们可以使用三数取中法进行优化，就是进入一趟排序之前，先将区间中间位置，开始位置，结束位置，他们三个数的中间大小的那个数与第一个数字交换，这样如果数组是有序的，就可以避免最坏情况的出现，因为每次将数组中间那个值换到begin的位置当作key，就可以使得每次排序后接近二分。
但是可能有人还会想这样一个问题，比如，多加了一个求三数取中的函数，函数的调用栈帧的创建是不是会增加时间的消耗呢？例如100w个数，会多100w次函数调用，说答案，其实是不会的，因为cpu对于函数调用的优化是很快的，就算是多调用了100w次，也不会差距几毫秒，但是对于这个问题，我们还有一个优化，就是小区间优化，比如我们递归的时候100w个数，每次二分到最后三次的时候，会产生219+218+2^17次调用（二叉树最后三层个数计算）这就是占据了80%以上的函数调用，这时候，我们可以进行小区间优化，当区间个数小于10的时候采用InsertSort，大于10，采用快排。就可以了。
代码如下
void QuickSort(int* arr, int begin, int end)
{
if (begin >= end)
return;
//三数取中对有序数组进行优化
int index = midnum(arr, begin, end);
Swap(&arr[begin], &arr[index]);
int left = begin;
int right = end;
int key = arr[begin];
int pivot = begin;
while(left < right)
{
while(left< right && arr[right] >= key)
{
--right;
}
arr[pivot] = arr[right];
pivot = right;
while(left < right && arr[left] <= key)
{
++left;
}
arr[pivot] = arr[left];
pivot = left;
}
pivot = left;
arr[pivot] = key;
//小区间优化
if ((pivot - 1 - begin+1) > 10)
{
QuickSort(arr, begin, pivot - 1);
}
else
{
InsertSort(arr + begin, pivot - 1 - begin + 1);
}
if ((end - pivot - 1 + 1) > 10)
{
QuickSort(arr, pivot + 1, end);
}
else
{
InsertSort(arr + pivot + 1, end - pivot - 1 + 1);
}
//QuickSort(arr, begin, pivot - 1);
//QuickSort(arr, pivot + 1, end);
}
快速排序版本2：左右指针法
因为左右指针法和挖坑法，在第一次排完序之后各个数字的位置不同，在选择题中可能会遇到，所以这里我会都介绍一下的。能写出一种即可。
void QuickSort2(int* arr, int begin, int end)
{
if (begin >= end)
return;
int left = begin;
int right = end;
int key = left;
while (left < right)
{
while (left < right && arr[right] >= arr[key])
right--;
while (left < right && arr[left] <= arr[key])
++left;
Swap(&arr[left], &arr[right]);
}
Swap(&arr[key], &arr[left]);
QuickSort2(arr, begin, left - 1);
QuickSort2(arr, left+1, end);
}
快速排序版本3：前后指针法
首先定义一个前指针prev，然后一个在后面的指针cur，cur先移动，去数组后面找小于arr[keyi]的值，找到了就++prev然后交换prev位置的值和cur位置的值，相当于是把小于key的值向前扔，大于key的值向后扔。最后cur走到数组尾部，prev指向最后一个小于key的值，将arr[keyi]于arr[prev]交换即可。
//前后指针法
void QuickSort3(int* arr, int begin, int end)
{
if (begin >= end)
return;
//三数取中对有序数组进行优化
int index = midnum(arr, begin, end);
Swap(&arr[begin], &arr[index]);
int keyi = begin;
int prev = begin;
int cur = begin + 1;
while (cur <= end)
{
while (arr[cur] < arr[keyi] && ++prev != cur)
{
Swap(&arr[cur], &arr[prev]);
}
++cur;
}
Swap(&arr[keyi], &arr[prev]);
QuickSort3(arr, begin, prev - 1);
QuickSort3(arr, prev + 1, end);
}
非递归借助栈实现递归
我们知道将递归转为非递归有两种方式：1，循环（比如一些简单的递归，斐波那契数列）2，用数据结构的栈模拟函数递归时候的系统栈帧。
那么为什么我们不用递归实现呢？这里说一下递归的缺点，其实并不是效率低，因为当代cpu对于递归的优化，递归效率以及不低了，比如上面的堆排序和递归实现的排序效率i其实并没有差很大。
不用递归的主要原因是，系统的栈空间是有限的一般是8M或者10M，超出这个就会发生错误StackOverflow。还有在一些微型计算机里面，往往栈空间较小。很容易栈溢出。
思想是：先把区间左右坐标入栈，然后进入循环栈为空的时候就退出循环，循环中先取出左右区间，先入右区间，先取出来的就是左区间，然后进行单趟排序，如果排完序后左右区间有两个及以上元素，就再次入栈。
int one_quick(int* a,int left,int right)
{
int begin = left;
int end = right;
int pivot = begin;
int key = a[pivot];
while (begin < end)
{
while (begin < end && a[end] >= key)
{
end--;
}
a[pivot] = a[end];
pivot = end;
while (begin < end && a[begin] <= key)
{
begin++;
}
a[pivot] = a[begin];
pivot = begin;
}
a[pivot] = key;
return pivot;
}
void QuickSort_St(int* a, int left, int right)
{
if (left >= right)
return;
Stack s1;
StackInit(&s1);
StackPush(&s1, right);
StackPush(&s1, left);
while (!StackEmpty(&s1))
{
int begin = StackTop(&s1);
StackPop(&s1);
int end = StackTop(&s1);
StackPop(&s1);
int pivot = one_quick(a, begin, end);//单趟排序
if (pivot + 1 < end)
{
StackPush(&s1, end);
StackPush(&s1, pivot + 1);
}
if (begin < pivot - 1)
{
StackPush(&s1, pivot - 1);
StackPush(&s1, begin);
}
}
}
计数排序
这里计数排序就是用一个数组记录每个数字出现的次数，用到了哈希表的映射。映射在排序这里有两种映射，一种是绝对映射（就是把元素值直接作为数组下标，用该下标对应的值来表示这个数字出现的次数）另一种是相对映射，就是先遍历数组，找出最大值和最小值，记为max，和min，要排序的数据就在min和max之间，我们就可以只开一个max-min+1大小的数组，映射的时候将元素值-min映射到哈希表中，取出来的时候再将下标+min，这个算法时间复杂度是O（N+range）range = max - min +1；空间复杂度是O（range）可以看出当数据范围较小而且数据很集中的情况下，range很小，这个排序的速度就会很快。
void Counting_Sort(int* a, int n)
{
//找出最大的和最小的
int max = a[0];
int min = a[0];
for (int i = 1; i < n; i++)
{
if (a[i] > max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}
}
int* hash = (int*)malloc(sizeof(int) * (max - min + 1));
//memset(hash, 0, sizeof(int) * (max - min + 1));
for (int i = 0; i < (max - min + 1); i++)
{
hash[i] = 0;
}
for (int i = 0; i < n; i++)
{
++hash[a[i]-min];//相对映射(也可以解决负数不能作为数组下标问题）
}
int j = 0;//记录拷贝下标
for (int i = 0; i < max - min + 1; i++)
{
while (hash[i])
{
a[j++] = i + min;
--hash[i];
}
}
}
基数排序
堆排序又称桶排序，实际中用到很少，就简单介绍一下思想。就是先将所有的数字按照个位升序排序，然后再按照十位，然后百位，知道这一组数据中的最高位，不足最高位的看作是0.
算法思想：先建堆（升序建大堆）建堆使用从下向上建堆，选择倒数第一个子树不为0
NULL的父节点开始一次向上建堆。使用向下调整算法（时间复杂度是O（N）），建堆完成后，将堆顶的元素与数组最后的元素交换位置，因为大堆堆顶一定是最大的元素，然后将数组长度缩减1，对n-1个数向下调整，（向下调整的前提条件是：左右子树都是大堆），因为交换只改变了堆顶的元素，所以满足条件，直接向下调整即可。直到数组只剩下一个元素，跳出循环，这时候排序结束。
大堆就是孩子节点都<=父节点，小堆就是孩子节点都>=父亲节点。
解释为什么升序要建大堆，因为如果是建的小堆，每次堆顶都是最小的元素，如果取出堆顶的元素，那么剩下的n-1个元素的再次取第二小的时候，树的结构已经乱了，就需要重新建堆O（N），这样堆排序就没有意义了。
void Swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void AdjustDown(int* a, int n, int root)
{
int parent = root;
int child = root * 2 + 1;
while (child < n)
{
if (child + 1 < n && 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;
}
}
void TestHeapSort()
{
int arr[] = { 1,0,9,8,7,4,6,5,3,2 };
int sz = sizeof(arr) / sizeof(arr[0]);
HeapSort(arr, sz);
Printarr(arr, sz);
}
