排序
插入排序
插入排序的前提是未插入时该序列有序。
假如是从小到大排序，插入的数为key，从右向左找小于等于key的值，如果不满足那么原来的向后移动一位进行覆盖，直到满足或者找完进行插入。 重复上面的操作。
cvoid InsertSort(int* a, int n)
{
int i = 0;
for (i = 0; i < n-1; i++)
{
int end=i;
int key = a[end + 1];
while (end>=0)
{
if (a[end] <= key)
break;
else
a[end + 1] = a[end];
end--;
}
a[end + 1] = key;
}
}时间复杂度O(n*n) 该排序适合接近有序的情况下，在该种情况下时间复杂度接近O(n)
希尔排序
有插入排序演变过来 希尔排序有两个步骤： 1.预排序（尽可能变得有序） 2.插入排序
例： 预排序：把待排序的一组数分为gap组，每一组进行插入排序
把这10组数分成3组： 第1组：2，5，3，0 第2组：4，1，8 第3组：6，9，7
经过预排之后的顺序
最后全部的进行插入排序，就可以得到有序的序列。 上面例子的代码：
cvoid ShellSort(int* a, int n)
{
int gap = 3;
for (int i = 0; i < n-gap; i++)
{
int end=i;
int key = a[end + gap];
while (end >= 0)
{
if (a[end] <= key)
break;
else
a[end + gap] = a[end];
end -= gap;
}
a[end + gap] = key;
}
InsertSort(a, n);
}希尔排序动态图
cvoid ShellSort(int* a, int n)
{
int gap = n;
while (gap>1)
{
gap = gap / 2;
for (int i = 0; i < n-gap; i++)
{
int end = i;
int key = a[end + gap];
while (end >= 0)
{
if (a[end] <= key)
break;
else
a[end + gap] = a[end];
end -= gap;
}
a[end + gap] = key;
}
}
}选择排序
选择排序很简单，每一次选出最小的反在前面，选出最大的放在后面。
cvoid SelectSort(int* a, int n)
{
int min, max;
int begin = 0, end = n - 1;
while (begin < end)
{
min = max = begin;
for (int i = begin; i <= end; i++)
{
if (a[min] > a[i])
min = i;
if (a[max] < a[i])
max = i;
}
swap(&a[min], &a[begin]);
//注意
if (begin == max)
max = min;
swap(&a[max], &a[end]);
begin++;
end--;
}
}注意两两交换的情况：
如果这4个下标指向的各不相同时，两两交换没有任何问题。
唯一要注意的情况是begin==max的时候，必须修改max，因为此时max的值不是最大而是变成最小，需要修改max，注意不能修改end，begin，end为边界控制。end==min的这种情况不需要修改，因为max没有变，还是要跑到最后的。
时间复杂度O(N*N)
堆排序
cvoid AdjustDwon(int* a, int n, int root)
{
int father = root;
int child = 2 * father + 1;
while (child <n)
{
if (child<n - 1 && a[child]<a[child + 1])
child++;
if (a[father] < a[child])
{
swap(&a[father], &a[child]);
father = child;
child = 2 * father + 1;
}
else
return;
}
}
void HeapSort(int* a, int n)
{
int i = 0;
for (i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDwon(a, n, i);
}
for (i = n - 1; i > 0; i--)
{
swap(&a[0], &a[i]);
AdjustDwon(a, i-1, 0);
}
}冒泡排序
cvoid BubbleSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
for (int i = begin; i < n-1; i++)
{
for (int j = begin; j < end; j++)
{
if (a[j+1] < a[j])
swap(&a[j], &a[j+1]);
}
end--;
}
}以前的文章
目录 桶排序（简化版） 冒泡排序 1.桶排序（简化版） 所谓桶排序就是桶的序列是排好的，只需要把数字放在对应桶的序列就可以，记下这个桶里面数字出现过几次就可以。 我们来排个数吧！3 4 6 8 5 2 9 7 1 我们需要的桶数由最大数+1构成，所以占内存比较大，但时间复杂度小。用数组来储存，arr[10],数组的下标是从0开始的。先把桶都先初始化为0，表示没有一个数出现过. 先讲一下一维数组的初始化 这是一种初始化
cppint arr[10] = { 0 };这样虽然初始化第一个元素，都是下面的各个元素都被默认为0 还可以这样初始化，下面的这种开始声明的并没有初始化，后续是进行的赋值
cppint arr[10];
int n = 0;
for (n = 0; n < 10; n++)
{
arr[n] = 0;
}在平时的初始化中我喜欢第一种。 下面我们循环输入刚才的数 3 4 6 8 5 2 9 7 1 并且把数存到相应的桶中，并记录出现几次
cppfor (n = 0; n < 9; n++)
{
scanf("%d", &s);
arr[s]++;
}接着我们把它输出就可以了（从小到大）
cppfor (n = 0; n < 10; n++)
{
if (arr[n] != 0)
printf("%d ", n);
}完整代码
cpp#include <stdio.h>
#define MAX 10
int main()
{
int arr[MAX]={0};
int n = 0,s=0;
for (n = 0; n < MAX-1; n++)
{
scanf("%d", &s);
arr[s]++;
}
for (n = 0; n < MAX; n++)
{
if (arr[n] != 0)
printf("%d ", n);
}
return 0;
}2.冒泡排序（基本思路前一个数与第二个数进行比较）
编辑 “冒泡”就像上面的图片一样，从下面到上面，我们这里讲的_冒泡排序 _就和这个类似 还是这样一个无序的数列** 3 4 6 8 5 2 9 7 1，我们想让它变成 1 2 3 4 5 6 7 8 9 假设有一个箭头J指向一个数 1）首先是J指向最下面的3， 它与J+1指向的数（也就是下一个数）进行比较，如果比它大，他俩就进行交换，否则不交换。然后J **往后走一步（j++），依此循环该步骤。直至到最后一个数的比较。这次找到的是最大的数。
cppfor (j = 0; j < 9 - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}2）3 4 6 5 2 8 7 1 9 ，这是上一步排成的，可以观察到最后一个数已经排好了（可以理解为最大的气泡已经出水面了），下面的排序就是把已经排好的数字（每次排好的最后一个数）去掉，按照（1）进行排下列的数字.直至完成排序。 注意： 1.总排序此时为排序数字个数减1 2.每一次排序都减1 完整代码
cppint main()
{
int arr[9] = { 3 ,4, 6, 8, 5, 2, 9 ,7, 1 };
int i, j;
for (i = 0; i < 9 - 1; i++)
{
for (j = 0; j < 9 - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return 0;
}感兴趣的小伙伴可以对上面的冒泡排序的算法进行优化哦
快速排序
快速排序的基本思路就是：选出一个基值，一般是选取最左边的为基值，然后从右边开始进行遍历，假设是按从小到大的顺序，那么从右边找小的，找到小的之后，在从左边开始找最大的，找到之后两者进行交换。然后继续重复上面的过程，直到左边大于等于右边的时候停止，然后和基数进行交换。 这是一轮
cint PartSort1(int* a, int left, int right)
{
int keyi = left;
while (left < right)
{
while (left < right && a[keyi] <= a[right])
right--;
while (left < right && a[left] <= a[keyi])
left++;
swap(&a[left], &a[right]);
}
swap(&a[keyi], &a[right]);
keyi = left;
return keyi;
}坑位法：把基数作为坑位，从右边开始找小（比基数小）的，找到之后填入坑位，该位置变成坑位，然后从左边开始找大，然后再填入坑位，直到找完（左边大于等于右边），把基数填入坑位。
cint PartSort2(int* a, int left, int right)
{
int keyi= left;
int temp = a[left];
while (left < right)
{
while (left<right&&a[right] >= temp)
{
right--;
}
a[keyi] = a[right];
keyi = right;
while (left < right && a[left] <= temp)
{
left++;
}
a[keyi] = a[left];
keyi = left;
}
a[keyi] = temp;
return keyi;
}前后指针法： 前指针从基数前一个位置开始，后指针从基数位置开始。前指针找小，当找到小的时候，后指针加一，然后前后指针指向的数值进行交换，然后前指针继续找小，直到查找完。
cint PartSort3(int* a, int left, int right)
{
int keyi = left;
int front = keyi + 1;
int back = keyi;
while (front <= right)
{
if (a[front] <= a[keyi])
{
back++;
swap(&a[front], &a[back]);
}
front++;
}
swap(&a[back], &a[keyi]);
keyi = back;
return keyi;
}上面描述的是一轮排序，每一轮排好之后，都可以确定好排好序之后基数的位置，基数左边是比它小的，右边是比它大的，左边继续排序，右边在继续排序。当还剩一个需要排序的时候就停止排序了。
cvoid QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
int keyi = left;
//keyi = PartSort1(a, left, right);
//keyi = PartSort2(a, left, right);
keyi = PartSort3(a, left, right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}上面这种排序还不可以，因为他的最坏的时间复杂度为O(N*N)，我们取的基数最好是该组有序数的中间值，但是这个值也不容易在无序中找到，此时我们用3数取中法，把最边的值，最右边的值，还有中间的值，3者进行比较，次大的为基数。为了保证还是上面的方法，我们把基数和最左边的数进行交换。
cint ThreeIn(int* a, int left, int right)
{
int middle = left + (right - left) / 2;
if (a[middle] < a[left])
{
if (a[left] < a[right])
return left;
else if (a[middle] < a[right])
return right;
else
return middle;
}
else
{
if (a[middle] < a[right])
return middle;
else if (a[left] < a[right])
return right;
else
return left;
}
}
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
int keyi = left;
int x = ThreeIn(a, left, right);
swap(&a[keyi], &a[x]);
//keyi = PartSort1(a, left, right);
//keyi = PartSort2(a, left, right);
keyi = PartSort3(a, left, right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}时间复杂度O(N*logN)
以最左边为基数，为什么从先右边开始呢？
在L与R交换的过程中没有什么可以讨论的，最主要的是相遇的时候和基数进行交换的情况： 1.R遇见L，此时L为最小的或者是基数，交换之后，左小右大。 2.L遇见R: (1)L与R没有交换 R所处的位置为小，R右边都是大，左边都是小，可以与基值进行交换。 (2)L与R交换 交换过后R还是会继续移动到小的地方，然后和(1)一样。
我们再讨论选左边为基值，还是讨论相遇的情况 1.L遇见R (1)没有发生交换就相遇了，无法判断相遇时与基值的大小。 (2)L与R交换过后再相遇，此时相遇的为大，不能和基值进行交换。 2.R遇见L R遇见L说明R与L交换过，此时基值是小的，可以交换。 综上所述:从左边开始并不能完全保证相遇的地方为小的。 非递归形式的快速排序 1.用栈进行实现 用栈储存一组数的上下界，如果从左开始选基数的话，根据栈的特性，我们先储存左边界，再储存右边界。每次排序都从栈中拿出2个数据。当向栈中储存边界的时候要主要边界直接有没有元素。
cvoid QuickSortNonR1(int* a, int left, int right)
{
Stack p;
InitStack(&p);
StackPush(&p, left);
StackPush(&p, right);
while (!StackEmpty(&p))
{
right = StackTop(&p);
StackPop(&p);
left = StackTop(&p);
StackPop(&p);
int keyi = PartSort3(a, left, right);
if (keyi + 1 < right)
{
StackPush(&p, keyi+1);
StackPush(&p, right);
}
if (keyi - 1 > left)
{
StackPush(&p, left);
StackPush(&p, keyi-1);
}
}
StackDestroy(&p);
}2.用队列实现 根据队列的性质，先储存右边界，再储存左边界。后面的过程和栈类似
cvoid QuickSortNonR2(int* a, int left, int right)
{
Queue p;
QueueInit(&p);
QueuePush(&p, right);
QueuePush(&p, left);
while (!QueueEmpty(&p))
{
right = QueueFront(&p);
QueuePop(&p);
left= QueueFront(&p);
QueuePop(&p);
int keyi = PartSort3(a, left, right);
if (keyi - 1 > left)
{
QueuePush(&p, keyi - 1);
QueuePush(&p, left);
}
if (keyi + 1 < right)
{
QueuePush(&p, right);
QueuePush(&p, keyi + 1);
}
}
QueueDestroy(&p);
}归并排序
归并排序是先把待排序的集合无限划分，直到划分为有序的区间（其实就是只含一个数)，对每个有序的区间进行归并，又得到了较大的有序区间，然后再归并，最后变成有序。这里在合并的时候需要开辟新的空间。
cvoid merge_sort(int* a, int* temp, int left,int right)
{
//控制返回的条件
if (left >= right)
return;
int mid = left + (right - left) / 2;
//不断分割区间left,mid],[mid+1,right]
merge_sort(a, temp, left, mid);
merge_sort(a, temp, mid+1, right);
//归并
int L1 = left, R1 = mid;
int L2 = mid+1, R2 = right;
int i = L1;
//区间存在
while (L1 <= R1 && L2 <= R2)
{
if (a[L1] <= a[L2])
temp[i++] = a[L1++];
else
temp[i++] = a[L2++];
}
while (L1 <= R1)
temp[i++] = a[L1++];
while (L2 <= R2)
temp[i++] = a[L2++];
memcpy(a+left, temp+left, sizeof(int) * (right - left+1));
}
void MergeSort(int* a, int n)
{
int* temp = (int*)malloc(sizeof(int) * n);
merge_sort(a, temp, 0,n-1);
free(temp);
}归并排序的非递归写法 从递归的里面可以发现，先是1个1个的归，然后是2个2个的归········· 在这个写法中，要注意边界的问题
cvoid MergeSortNonR(int* a, int n)
{
int* temp = (int*)malloc(sizeof(int) * n);
if (temp == NULL)
exit(-1);
int gap = 1;
//gap表示有几个几个有序，1为1个1个一组有序，2表示2个2个一组有序
while (gap < n)
{
int left1 = 0;
while (left1<n)
{
int right2 = left1 + 2*gap-1;
int mid = (left1 + right2) / 2;
int right1 = mid, left2 = mid + 1;
int i = left1; int x = left1;
if (right1 >= n)
{
right1 = n - 1;
left2 = n;
right2 = n-1;
}
else if (left2 >= n)
{
left2 = n;
right2 = n-1;
}
else if (right2 >= n)
{
right2 = n - 1;
}
while (left1 <= right1 && left2 <= right2)
{
if (a[left1] <= a[left2])
temp[i++] = a[left1++];
else
temp[i++] = a[left2++];
}
while (left1 <= right1)
temp[i++] = a[left1++];
while (left2 <= right2)
temp[i++] = a[left2++];
memcpy(a + x, temp + x, sizeof(int) * (right2 - x + 1));
left1 = right2 + 1;
}
gap *= 2;
}
free(temp);
}计数排序
给定一组数，确定该组数的范围（最大与最小之间的范围），申请在这范围内的空间，统计每个数出现的次数。最后从新拷贝到原数据中
cvoid CountSort(int* a, int n)
{
int min = a[0], max = a[0];
for (int i = 0; i < n; i++)
{
if (min > a[i])
min = a[i];
if (max < a[i])
max = a[i];
}
int range = max - min+1;
int* temp = calloc(range, sizeof(int));
for (int i = 0; i < n; i++)
{
temp[a[i] - min]++;
}
for (int i = 0,j=0; i < range; i++)
{
while (temp[i]--)
a[j++] = i + min;
}
}题目练习——力扣912.排序数组
腾讯云开发者
