目录
一、插入排序：
插入排序，顾名思义就是将所要排序时的那个插入进有序的数字里面。
思路:
给定一个数组,然后定义一个变量end和tmp
来个从1开始的循环，结束条件为:这个小于数组元素n
然后每次循环前将end定义为i-1,定义tmp为i处元素的值
在嵌套一个while循环,
在里面进行比较，如果tmp小于end处的值，就交换,然后再将end--
以来和前面全部元素进行比较。
(所以这个while循环的结束条件为end<0)
否则将end+ 1处的位置变为tmp
记得每次都是将tmp存储的值赋给end+1
void InserSort(int* a,int n)
{
for (int i = 1; i < n; i++)
{
int end = i - 1;
int tmp = a[i];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}二、希尔排序：
插入排序时希尔排序的一种特殊情况。
希尔排序就是将一组数据分为gap（一个整数）组，然后对每一组进行排序，是对插入排序的一种优化，然后继续重复上述分组和排序，当gap=1时，就排好序了。
下图就是gap = 3的分组情况。（红色一组，蓝色一组，绿色一组）
希尔排序：
1、首先分为若干组
2、对每一个子组进行插入排序，与上面不一样的就是每次都要跳过gap个元素。
3、逐渐减小gap的值，减小跳过的元素。
4、最后在进行一次插入排序即可
（这样感觉是不是很麻烦，但是因为每一次跳过的元素很多，比如说我有个数组9,8,7,6,5，4,3,2,1如果插入排序9就会要走8次，但是如果我对它进行分组之后，9就只走了3次，所以实际上希尔排序是比插入排序更快的）
void Print(int* a,int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap /= 2;//最后一次gap就等于1了
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = a[i + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
void TestShellSort()
{
int a[] = { 2,3,7,1,9,1,7,8,5,4 };
int n = sizeof(a) / sizeof(a[0]);
Print(a, n);
ShellSort(a, n);
Print(a, n);
}
int main()
{
TestShellSort();
return 0;
}三、冒泡排序：
思路：
1.从序列的第一个元素开始，依次比较相邻的两个元素，如果前面的元素大于后面的元素，则交换它们的位置。
2.继续比较相邻的元素，直到最后一个元素，这样最大的元素就会被交换到序列的最后一个位置。
3.对除了最后一个元素以外的其他元素重复上述步骤，直到整个序列有序。
int main()
{
int a[10] = { 4,2,8,5,0,1,5,7,3,9 };
int n = sizeof(a) / sizeof(a[0]);
for (int i = 0; i < n; i++)
{
for (int j = 1; j < n - i; j++)
{
if (a[j] < a[j - 1])
{
int tmp = a[j];
a[j] = a[j - 1];
a[j - 1] = tmp;
}
}
}
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
return 0;
}四、选择排序：
基本思想：
第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始(末尾)位置，
然后选出次小(或次大)的一个元素，存放在最大(最小)元素的下一个位置，
重复这样的步骤直到全部待排序的数据元素排完 .
void SelectSort(int* a, int n)
{
int i = 0;
for (i = 0; i < n; i++)//i代表参与该趟选择排序的第一个元素的下标
{
int start = i;
int min = start;//记录最小元素的下标
while (start < n)
{
if (a[start] < a[min])
min = start;//最小值的下标更新
start++;
}
Swap(&a[i], &a[min]);//最小值与参与该趟选择排序的第一个元素交换位置
}
}
五、快速排序：
1、霍尔法：
思路：
这里排序为升序
我们这里找最左边的元素作为key
定义一个变量指向最右边right，再来一个变量指向最左边left（注意，如果key在左边，那么就要从右边开始先走，如果key在右边，那么就要从左边开始走，这样才能保证这两个相遇的位置一定比key要小）
来个循环遍历这个序列：
right开始向左走找一个比key还要小的，
找到后left向右走找到一个比key还要大的，
接着交换这两个位置的元素。
所以结束条件就是left<right。
结束后交换此时这两个所在的共同位置和key的位置，key也要换到这个位置
最后再来递归即可（所以可以在最开始用两个变量begin和end记录left和right的位置）
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void QuickSort1(int* a, int left, int right)
{
if (left >= right)
return;
int begin = left, end = right;
//三数取中
int midi = GetMidNumi(a, left, right);
Swap(&a[left], &a[midi]);
int keyi = left;
while (left < right)
{
//右边先走找小的
while (left < right && a[right] >= a[keyi])
right--;
//左边走找大的
while (left < right && a[left] <= a[keyi])
left++;
if (left == right)
break;
Swap(&a[right], &a[left]);
}
Swap(&a[keyi], &a[left]);
keyi = left;
QuickSort1(a, begin, keyi - 1);//这里为左边的区间
QuickSort1(a, keyi + 1, end);//这里为右边的区间
}2、挖坑法：
思路：
首先，将第一个元素存放在临时变量key中，此时将第一个元素定义为hole，这个时候这个hole就可以随便改了。
接着像霍尔法一样，right向左走找比key小的位置，此时将这个位置的元素赋值给hole，然后将hole改到这个right所在的位置。
然后left向右走找比key大的位置，找到后将这个位置的元素赋值给hole，然后将hole改到这个left所在的位置。
直到left == right后退出循环，此时将最开始的变量key放在hole中
最后左递归的区间为[begin, hole - 1]
右递归的区间为[ hole + 1, end]
void QuickSort2(int* a, int left, int right)
{
if (left >= right)
return;
//三数取中
int midi = GetMidNumi(a, left, right);
Swap(&a[left], &a[midi]);
int key = a[left];
int begin = left, end = right;
int hole = left;
while(left < right)
{
while (left < right && a[right] >= key)
right--;
//Swap(&a[hole], &a[right]);
a[hole] = a[right];
hole = right;
while (left < right && a[left] <= key)
left++;
//Swap(&a[hole], &a[left]);
a[hole] = a[left];
hole = left;
}
a[hole] = key;
QuickSort2(a, begin, hole - 1);
QuickSort2(a, hole + 1, end);
}3、前后指针法：
思路：
首先：定义最左边为key，然后最左边为prev，prev的下一个为cur
然后如果cur所在的值小于key，那么++prev，然后将cur所在的值和prev所在的值相交换，在cur++。
如果cur的值不小于key，那么就cur++。
退出循环的条件为cur小于right。
最后交换此时prev所在的元素和最左边的元素。
int QuickSort3(int* a, int left, int right)
{
// 三数取中
int midi = GetMidNumi(a, left, right);
if (midi != left)
Swap(&a[midi], &a[left]);
int keyi = left;
int prev = left;
int cur = left + 1;
while (cur <= right)
{
if (a[cur] < a[keyi])
{
prev++;
Swap(&a[cur], &a[prev]);
cur++;
continue;
}
else
{
cur++;
continue;
}
}
Swap(&a[prev], &a[keyi]);
keyi = prev;
return keyi;
}void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
int keyi = QuickSort3(a, left, right);
QuickSort3(a, left, keyi - 1);
QuickSort3(a, keyi + 1, right);
}4、非递归的实现：
思路：
因为递归可能会存在栈溢出，那么就需要把这个程序修改为非递归。
那么就需要栈和循环来帮助我们实现递归转非递归。
1、首先将这个序列的right先入栈，再将left入栈（顺序其实是无伤大雅的），
2、然后来个循环，结束条件为这个栈为空
3、在循环中定义begin访问栈顶的元素，就是上面的left（left后入栈的）
定义end访问栈顶元素的下一个为right。
4、接着用QuickSort3来进行单趟排序，返回值记录在keyi中。
所以里面区间就变成了：[begin,keyi-1] keyi [keyi+1, end]（左边比keyi小，右边比keyi大）
5、接着判断，如果keyi+1小于end，那么依次将end和keyi+1入栈，
如果keyi-1大于begin，那么将依次将keyi-1和begin入栈。
所以此时循环上去就继续访问栈顶元素和栈顶元素的下一个来作为begin和end继续排序。
void QuickSortNonR(int* a, int left, int right)
{
ST st;
STInit(&st);
STPush(&st, right);
STPush(&st, left);
while (!STEmpty(&st))
{
int begin = STTop(&st);
STPop(&st);
int end = STTop(&st);
STPop(&st);
int keyi = QuickSort3(a, begin, end);
// [begin,keyi-1] keyi [keyi+1, end]
if (keyi + 1 < end)
{
STPush(&st, end);
STPush(&st, keyi+1);
}
if (begin < keyi-1)
{
STPush(&st, keyi-1);
STPush(&st, begin);
}
}
STDestroy(&st);
}六、堆排序：
思路：
首先要有一个向下调整建堆的实现：
void AdjustDown(HPDataType* a, int n, int parent)
{
assert(a);
int child = parent * 2 + 1;
while (child < n)
{
//大堆
//选出左右孩子中大的那一个
//最好别访问后再来
// if ( a[child + 1] > a[child] && child + 1 < 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;
}
}
}
思路：
1、给定一个数组，然后对其进行排序
2、既然是堆排序，那么首先就要创建一个堆，这里有两种方法建堆，分别是向下调整建堆和向上调整建堆。
3、建好这个堆后，再来个循环（这个数组有多少个就循环多少次），在里面先将最后一个与第一个相交换（此时树根在第一个，它是最大的）（目的是将树根位置放到最后一个实现排序），交换后再对这个堆进行向下调整，最后将访问这个堆的个数减一（因为最大的已经排序好了，就不用管了。
注意：
排升序建大堆，不能建小堆，因为最上面的是排好了，但是下面的就不能成为一个堆了，选了最小的就不能选次小的了，剩下的看作堆，选次小的，但是关系全乱了，所以就要重新建堆，这个时候时间复杂度N*logN就比较大
所以就是要排升序建大堆。
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[end], &a[0]);
AdjustDown(a, end, 0);
end--;
}
}七、归并排序：
1、递归实现：
思路：
首先定义tmp指针指向一个与原数组大小一样的空间，作用是存放拷贝过去的值。
然后再将要分解的序列的中间值给算出来，就知道区间了，就可以进行递归分解了，
最后在返回时进行重新排序合并，再将虚拟数组的值拷贝回去就可以了。
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\n");
return;
}
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
}解析：
1、有一个MergeSort函数，创建一个tmp指针指向一个与原数组大小一样的空间，作用是存放拷贝过去的值。
2、_MergeSort是归并排序的核心，分割后的区间[begin,mid][mid+1,end]所以将上述两个进行递归即可。
3、具体合并操作：
首先定义begin1，end1为一个的区间，begin2，end2为另一个区间，然后进行判断大小，越小的那个放在tmp中，最后如果二者只要有一个走完了，就可以进行判断，将未走完的那个数组剩下的元素放在tmp的后面。
4、最后将tmp中的值拷贝回数组a中即可。
2、非递归实现：
非递归实现的时候，定义一个gap（这个是归并过程中，每一组数据的个数）
依然需要嵌套循环来完成这个非递归的实现
所以就需要将上述的begin1，end1，begin2，end2改为
因为是取左闭右闭的区间，所以end1需要i+gap后-1（跳过每组数据的个数）
begin2比end1大1，end就需要跳过两个gap所以乘以2。
特别注意！！！！！！！！
这里因为end1，begin2，end2，是加上gap的，当gap较大时就会发生越界访问，所以要对它们进行越界处理。
三种情况的越界：
1、end1,begin2,end2越界，解决方法：不归并了（修正为一个不存在的区间）
2、begin2,end2越界，解决方法：不归并了
3、end2越界，解决方法：修正end2继续归并
void MergeSortRenN(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail\n");
return;
}
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
int j = i;
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 - 1;
}
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 , tmp , sizeof(int) * n);
gap *= 2;
}
free(tmp);
}八、计数排序：
思路：
遍历一遍原数组，然后统计每一个元素出现的个数放在计数数组中（计数数组的大小通过原数组的end-begin+1来计算）（计数数组的初始化用calloc来初始化，这样可以将数组中的元素全员设置为0方便计数），在通过遍历计数数组中每一个元素出现的次数情况进行排序。
比如：2出现了3次，3出现了2次，5出现了2次......
而有：2,2,2,3,3,5,5......
注意：要使用相对位置映射计数，这样的话可以避免待排序数组较大时，在前面开辟过大的空间造成空间浪费。
局限性：只适合范围集中且范围不大的整形数组，不适合范围较大或者非整型的排序。
优化：计数时，将所记的数减去这个数组中最小的数，来达到相对位置映射，记得在最后加回那个最小的数字即可
void CountSort(int* a, int n)
{
//初始化
int max = a[0];
int min = a[0];
for (int i = 0; i < n ; i++)
{
if (a[i] > max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}
}
int range = max - min + 1;
int* countiA = (int*)calloc(range, sizeof(int));
if (countiA == NULL)
{
perror("calloc fail");
return;
}
//计数
for (int i = 0; i < n; i++)
{
countiA[a[i] - min]++;
}
//排序
int j = 0;
for (int i = 0; i < range; i++)
{
while (countiA[i]--)
a[j++] = i + min;
}
free(countiA);
} 标签：归并,right,end,int,gap,计数,冒泡,排序,left From： https://blog.csdn.net/2301_79571285/article/details/139394471湖北师范大学计算机与工程王飘然
----------------湖北师范大学计信学科小组