常见排序的总结
插入排序
基本思想
每一步将一个待排序的元素，按其排序码的大小，插入到前面已经排好序的一组元素的合适位置上去，直到元素全部插完为止
直接插入排序
代码实现
//插入排序
void InsertSort(int *arr, int n)
{
int index = 0;
assert(arr);
for(index = 1; index < n; index++)
{
//将当前数据往前插入
int end = index-1;
int temp = arr[index];
while(end >= 0 && temp < arr[end])
{
arr[end+1] = arr[end];
--end;
}
arr[end+1] = temp;
}
}
下图只是演示到将16排序到前面的过程
直接插入排序的优化
//插入排序
void InsertSort_OP(int *arr, int n)
{
int index = 0;
for (index = 1; index < n; index++)
{
int temp = arr[index];
//通过二分查找 找出待插入元素的位置
int left = 0;
int right = index - 1;
while (left <= right)
{
int mid = left + ((right - left) >> 1);
if (temp >= arr[mid])
left = mid + 1;
else
right = mid - 1;
}
//将当前数据往前插入
int end = index - 1;
//搬移元素
while (end >= left)
{
arr[end + 1] = arr[end];
--end;
}
arr[left] = temp;
}
}
由于之前的序列都是有序的，这样的话就不用一个一个进行比较，只要先用二分查找找到插入的位置，这样的话本来需要搬运元素只需要搬运一次就行，很多元素不需要比较一次就搬运一次，这样会提高效率！
总结
元素集合越接近有序，直接插入排序算法的时间效率越高！ 最优情况下：时间效率为$O(n)$ 最差情况下：时间复杂度为$O(n^2)$ 空间复杂度：$O(1)$，它是一种稳定的排序算法
希尔排序
又称缩小增量排序，是对直接插入排序的优化
很容易看出，经过这样的分组之后，许多比较大的数字都放在了后面，小数字都放在了前面，只要gap不断减小，分组不断变小，最后直到gap减到1的时候就和直接插入排序没什么区别了！
代码实现
void ShellSort(int* arr,int len)
{
int gap = len;
assert(arr);
while(gap>1)
{
gap = gap/3+1;
int cur = 0;
for(cur = gap;cur<len;++cur)
{
int end = cur-gap;
int tmp = arr[cur];
while(end>=0 && tmp<arr[end])
{
arr[end+gap] = arr[end];
end -= gap;
}
arr[end+gap] = tmp;
}
}
}
总结
希尔排序是一种不稳定的排序，时间复杂度：$N^{1.25} 到 1.6N^{1.25}$
选择排序
基本思想
假设要排升序，每一趟选择一个最大的数字与最后的元素交换，这里所说的最后一个元素是会逐步向前调整的！
代码实现
//选择排序
void SelectSort(int *arr, int n)
{
int index = 0;
assert(arr);
for (index = 0; index < n; index++)
{
int maxPos = 0;
int i = 1;
//找最大元素的位置
for (i = 1; i < n-index; i++)
{
if (arr[i] > arr[maxPos])
maxPos = i;
}
if (maxPos != (n - index - 1))
Swap(&arr[maxPos], &arr[n-index-1]);
}
}
基本选择排序的优化
优化为每趟寻找最大值的同时找到最小值
//选择排序的优化
void SelectSort_OP(int *arr, int n)
{
int begin = 0;
int end = n-1;
assert(arr);
while(begin < end)
{
int minindex = begin;
int maxindex = begin;
//分别找到最大和最小的下标
int i = 0;
for(i = begin;i <= end; ++i)
{
if(arr[i]>arr[maxindex])
{
maxindex = i;
}
if(arr[i]<arr[minindex])
{
minindex = i;
}
}
//把最小的放在前面，最大的放在后面
Swap(&arr[begin], &arr[minindex]);
if(begin == maxindex)//修正
maxindex = minindex;
Swap(&arr[end], &arr[maxindex]);
++begin;
--end;
}
}
只不过这种优化的方式需要注意一点（见下图），如果最小的元素恰好是最大的元素需要插入的位置，此时就需要将minPos设置为原来max的位置，因为最小值已经和maxPos位置的值交换了！
总结
时间复杂度：$n^2$ 空间复杂度：$O(1)$ 这是一种不稳定的排序
堆排序
堆排序有两个关键点
- 根据数组去建堆
- 交换首尾元素向下调整
代码实现
void HeapAdjust(int *arr,int root,int len)
{
//child是左孩子的下标
int child = root*2+1;
assert(arr);
while(child<len)
{
// 比较左孩子和右孩子,child指向大的孩子
if(child+1<len && arr[child+1]>arr[child])
{
child++;
}
// 1.若大的孩子节点大于根节点,则不再需要调整,跳出循环
// 2.否则,交换孩子节点和根节点,将根节点继续往下调整
if (arr[child] > arr[root])
{
Swap(&arr[child], &arr[root]);
root = child;
child = child * 2 + 1;
}
else
return;
}
}
//堆排序
void HeapSort(int *arr, int len)
{
int i = (len - 2)>>1;
assert(arr);
//建堆
for( ; i>=0; i--)
HeapAdjust(arr, i, len);
//排序
for(i = len-1;i > 0; i--)
{
Swap(&arr[i], &arr[0]);
HeapAdjust(arr, 0, i);
}
}
总结
堆排序的时间复杂度：$N/2 *{log N}$其实就是$logN$ 空间复杂度：$O(1)$ 稳定性：不稳定
交换排序
冒泡排序
冒泡排序的思想非常简单，如下图，两两比较，每趟排序总可以把最大的放在最后面或者最小的值放在最后面，只需要进行（假设元素个数为n）n-1趟冒泡，便可以排序完成！
代码实现
// 冒泡排序及其优化
void BubbleSort(int* arr, int len)
{
int index = 0;
int end = 0;
assert(arr);
for(end = len-1;end>0;end--)
{
int flag = 0;
for(index=0;index<end;index++)
{
if(arr[index]>arr[index+1])
{
Swap(&arr[index], &arr[index+1]);
flag = 1;
}
}
if(flag == 0)
break;
}
}
总结
冒泡排序最好情况时间复杂度$O(n)$，冒泡排序最坏情况下时间复杂度 $O(1)$ 冒泡排序空间复杂度$O(1)$ 冒泡排序是一种稳定的排序算法
快速排序
基本思想
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
这样的话左边都是比基准值小的，在右边的都是比基准值大的，根据分治的思想，可以再把左边的序列选出一个基准值，在右边的序列也选择一个基准值，左边的排好了，右边的排好了，整个序列也就排好了！
代码实现_hoare版本
//快速排序
int PartSort(int *a, int left, int right)
{
int key = a[right];
int begin = left;
int end = right - 1;
while (begin < end)
{
//找比基准值大的
while ((begin < end) && (a[begin] <= key))
begin++;
//找比基准值小的
while ((begin < end) && (a[end] >= key))
end--;
if (begin<end)
Swap(&a[begin], &a[end]);
}
//最后别忘记把基准值和相遇点交换
if (begin != right - 1)
Swap(&a[begin], &a[right-1]);
return begin;
}
void QuickSort(int *a, int left, int right)
{
assert(a);
if (left >= right)
return;
int div = PartSort(a, left, right);
QuickSort(a, left, div);
QuickSort(a, div + 1, right);
}
前后指针法
这个方式其实不难理解，就是每次将key值移动到中间，在key左边的值都是比key小的值，key右边的值都是比key大的值，这样做分组的的话通过递归就可以完成排序！
int PartSort3(int *array, int left, int right)
{
int key = array[right - 1];
int cur = left;
int pre = cur - 1;
while (cur < right)//说明区间的元素还没有遍历完成
{
if ((array[cur] < key) && (++pre != cur))
Swap(&array[cur], &array[pre]);
++cur;
}
if (++pre != right)
Swap(&array[pre], &array[right-1]);
return pre;
}
void QuickSort3(int *a, int left, int right)
{
assert(a);
if (left >= right)
return;
int div = PartSort3(a, left, right);
QuickSort(a, left, div - 1);
QuickSort(a, div + 1, right);
}