1.直接插入排序
插入排序的基本思想 ：
有一个有序区间，插入一个数据，依旧有序
代码
//直接插入排序
//思路 比较end当前位置和tmp下个位置，如果大于就替换，还会往后比较end往后的数和tmp的值比较，如果大于就替换，完成有序
void InserSort(int* a, int sz)
{
for (int i = 0; i < sz-1; i++)
{
int end = i;
//当趟排序[0, end]有序 end+1位置的值，插入进入，保持他依旧有序
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
//当end=0的时候tmp又小于end实行交换，但只交换了end的值，tmp的值没插入进去，所以在这里插入，而不是在循环里面插入tmp
a[end + 1] = tmp;
}
}
2.希尔排序
思路：
和直接插入排序差不多但是多了个预排序
预排序就是让大的数更快到后面，小的数更快到前面
代码
//希尔排序
void ShellSort(int* a, int sz)
{
//1.n>1预排序
//2.n==1直接插入排序
int gap = sz;
while (gap > 1)
{
gap = gap / 3+1;
for (int i = 0; i < sz-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;
}
}
}
3.快排
快排有很多变种
1.hoare
这是快排最开始的一种
思路：
让右边找比key小，左边找key大，找到就交换，如果它们相遇就把相遇的位置和key交换，但是这样有个问题就是怎么保证最后交换的值有序
左边做key,右边先走,右边做key左边先走
右边做key也是一样的
代码
//hoare
//思路 用right找比key小，left找比key大，找到就交换left和right，如果left和right相遇就和key的值交换
int PartSort1(int* a, int left, int right)
{
int key = left;
while (left < right)
{
//找小
if (left < right && a[right] >= a[key])
{
right--;
}
//如果不等于的话 5 5 2 3 5这种情况会死循环
//但是如果这样的话 1 2 3 4 5，会有越界的风险
//找大
if (left < right && a[left] <= a[key])
{
left++;
}
swap(&a[left], &a[right]);
}
//出来就是left和right相遇的时候
swap(&a[key], &a[right]);
return left;
}
void QuickSort1(int* a, int begin, int end)
{
//子区间相等或者只有一个值代表递归结束
if (begin >= end)
{
return;
}
//被分割成【begin key-1】 key 【key+1 end 】
int key = PartSort1(a, begin, end);
QuickSort1(a, begin, key - 1);
QuickSort1(a, key + 1, end);
}
2.挖坑法
思路:
存key的值，右边找小，找到右边的值赋给坑位，再把右边的位置变为坑，左边找大找到把左边的值给坑位，再把左边的位置变为坑
//左边和右边相遇的格子是坑位，把key的值赋给坑位
代码
/挖坑法
//思路 存key的值，右边找小，找到右边的值赋给坑位，再把右边的位置变为坑，左边找大找到把左边的值给坑位，再把左边的位置变为坑
//左边和右边相遇的格子是坑位，把key的值赋给坑位
int PartSort2(int* a, int left,int right)
{
int key = a[left];
int pit = left;
while (left<right)
{
//找小
while(left < right && a[right] >= key)
{
right--;
}
a[pit] = a[right];
pit = right;
//找大
while(left < right && a[left] <= key)
{
left++;
}
a[pit] = a[left];
pit = left;
}
a[pit] = key;
return pit;
}
3.前后指针法
思路:
cur找到比key小的值和prev交换再把prev++，cur循环结束把key和prev交换
代码
//前后指针法
//思路 cur找到比key小的值和prev交换再把prev++，cur循环结束把key和prev交换
int PartSort3(int* a, int left, int right)
{
//让快排不要每次选到最小和最大的数
int mid = GetMidIndex(a, left, right);
swap(&a[left], &a[mid]);
int key = left;
int cur = left + 1;
int prev = left;
while (cur <= right)
{
if (a[cur] <= a[key] && a[prev++] != a[cur])
{
swap(&a[cur], &a[prev]);
}
cur++;
}
swap(&a[key], &a[prev]);
return prev;
}
void QuickSort1(int* a, int begin, int end)
{
//子区间相等或者只有一个值代表递归结束
if (begin >= end)
{
return;
}
//被分割成【begin key-1】 key 【key+1 end 】
int key = PartSort3(a, begin, end);
QuickSort1(a, begin, key - 1);
QuickSort1(a, key + 1, end);
}
4.非递归快排
思路:
用栈来模拟递归遍历整个数组
代码
//非递归快排
void QuickSort3(int* a, int left, int right)
{
ST st;
StackInit(&st);
StackPush(&st, left);
StackPush(&st, right);
while (!StackEmpty(&st))
{
//后进先出
int right = StackTop(&st);
StackPop(&st);
int left = StackTop(&st);
StackPop(&st);
int key = PartSort2(a, left, right);
if (left < key - 1)
{
StackPush(&st, left);
StackPush(&st, key-1);
}
if (key + 1 < right)
{
StackPush(&st, key+1);
StackPush(&st, right);
}
}
StackDestory(&st);
}
