- 冒泡排序
- 快速排序
- 递归版本
- hoare版本
- 挖坑法
- 前后指针法
- 非递归版本
时间复杂度 (O(N*N)) 冒泡排序是稳定的排序
代码如下，这里我加了优化，即有序(没有交换过)不再继续冒泡，虽然可能没什么用
for (int j = 0; j < n; j++)
{
int exchange = 0;
for (int i = 1; i < n - j; i++)
{
if (a[i - 1] > a[i])
{
exchange = 1;
Swap(&a[i - 1], &a[i]);
}
}
if (exchange == 0)
{
break;
}
}
快速排序
时间复杂度 O(N * logN) 快排不是稳定排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
升序
主要思想也就是先定一个关键字，然后两个指针在数组两头往中间走（前提是左右不能先相遇），让右边先走，直到遇到比关键字小的停下来，让左边走，直到遇到比关键字大的，两个值交换，然后继续让右边…直到相遇，此时再把关键字的值与相遇的值交换，这样就得到了一个左边是比关键字小，右边比关键字大的序列。然后分成两个子区间分别排一次，一直递归下去，就可以完成排序。
但是这个排序排有序情况就会很糟糕，因为每次分出一个值，那如果让它能够每次都能平均分成两份，这样面对特殊情况，效率也会很高了。
所以我们选择了用三数取中就，解决这种特殊情况，这样每次都能拿到中位数周围的值，效率大大地提高
int GetMidIndex(int* a, int left, int right)
{
int mid = left + (right - left) / 2;
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return left;
}
else
{
return right;
}
}
else
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}
//如果左边做key，右边先走，右边做key，左边先走
int PartSort1(int* a, int left, int right)
{
int midi = GetMidIndex(a, left, right);
Swap(&a[midi], &a[left]);
int key = left;
while (left < right)
{
//右边找小，没找到就减减
while (left < right && a[key] <= a[right])//这里left < right 和 = 很关键，如果没有就会死循环
{
--right;
}
//左边找大，没找到就加加
while (left < right && a[key] >= a[left])
{
++left;
}
Swap(&a[left], &a[right]);
}
Swap(&a[right], &a[key]);
return left;
}
void QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
//小区间优化，让递归次数大大减少
if (right - left + 1< 10)
{
InsertSort(a + left, right - left + 1);
}
else
{
int key = PartSort3(a, left, right);
QuickSort(a, left, key - 1);
QuickSort(a, key + 1, right);
}
}
挖坑法
升序
其思想就是，先把最左边(key)的位置记录下来，就相当于这里是一个坑(pivot)，然后右边找到了比key的值小的值，就把之前的坑填上(也就是用新的值覆盖掉之前key的值)，再把自己变成新坑(给pivot赋值)。然后左边走找到比key大的值，把刚刚形成的坑给填了，自己又变成新坑。最后左右指针相遇，就把最前面key记录下来的值放到相遇的位置，就完成了一次循环。
int PartSort2(int* a, int left, int right)
{
int midi = GetMidIndex(a, left, right);//得到中间值
Swap(&a[midi], &a[left]);
int pivot = left;
int key = left;//把第一个值存起来
while (left < right)
{
while (a[right] >= a[key] && left < right)
{
--right;
}
a[pivot] = a[right];//填掉之前的坑
pivot = right;//自己变成新的坑
while (a[left] <= a[key] && left < right)
{
++left;
}
a[pivot] = a[left];
pivot = left;
}
a[pivot] = a[key];//把之前存起来的第一个值放到坑里，这里就完成了一趟
return pivot;
}
前后指针法
升序
其思想就是先定义两个指针 cur prev ，然后让cur先走，直到遇到比关键值小的，就停下来，让prev向后面走一步，然后交换这两个值，最后，当cur走完整个数组，将关键值与prev指向的值交换，循环往复。
这种方法可能理解起来有点困难。但是代码量很少。
int PartSort3(int* a, int left, int right)
{
int midi = GetMidIndex(a, left, right);
Swap(&a[midi], &a[left]);
int key = left;
int cur = left + 1;
int prev = left;
while (cur <= right)
{
if (a[cur] < a[key] && ++prev != cur)
{
Swap(&a[cur], &a[prev]);
}
++cur;
}
Swap(&a[prev], &a[key]);
return prev;
}
非递归版本
主要是利用了栈数据结构的性质，存储了需要排序的区间。
void QuickSortNonR(int* a, int left, int right)
{
SN* st = StackInit();
StackPush(st, left);
StackPush(st, right);
while (!StackEmpty(st))
{
int end = StackTop(st);
StackPop(st);
int begin = StackTop(st);
StackPop(st);
int key = PartSort3(a, begin, end);
if (key + 1 < end)
{
StackPush(st, key + 1);
StackPush(st, end);
}
if (key - 1 > begin)
{
StackPush(st, begin);
StackPush(st, key - 1);
}
}
StackDestroy(st);
}
多的不说，快排。
