1、排序的概念
2、常见的排序算法
1、基本思想：
2、基本过程
图解：
代码实现：
void InsertSort(int *arr, int n)
{
for (int i = 0; i < n - 1; ++i)
{
int end = i;//end有序数列最后一个元素的下标
int temp = arr[end + 1];//temp待插入的元素
while (end >= 0)
{
if (temp <= arr[end])
{
arr[end + 1] = arr[end];
--end;
}
else
break;
}
arr[end + 1] = temp;
}
}
总结：
1、再待排序的元素当中，假设前n-1个元素都是已经排好序的，然后将第n个元素插入到已经排好的序列当中，使得前n个元素有序，按照此种方法将数据进行插入，直到完全有序。
2、在此排序中我们在所有数据没有完全插入以前，并不能确定每个数据的位置，直到所有数据完全插入。
3、元素集合越接近有序，插入排序算法的时间效率就越高
4、时间复杂度：O(N^2)
5、空间复杂度：O(1)，它是一种稳定的排序算法
6、稳定性：稳定
1、基本思想
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数n，把待排序文件中所有记录每隔n进行分组，并将距离为n的元素分为一组，然后再进行插入排序，在取一个比小的数，重复上述操作，直到n等于1为止。
2、基本步骤
void ShellSort(int *arr, int n)
{
int gap = n;
while (gap > 1)
{
//每次将gap缩小一半
gap /= 2;
for (int i = 0; i < n-gap; ++i)
{
int end = i;
int temp = arr[end + gap];
while (end >= 0)
{
if (temp < arr[end])
{
arr[end + gap] = arr[end];
end-=gap;
}
else
break;
}
arr[end+gap] = temp;
}
}
}
特性总结：
1、希尔排序是对直接插入排序的优化。
2、当gap>1时都是预排序，目的是让数组更接近于有序。当gap==1时，数组已经接近于有序了，这样就会很快。这样整体而言，可以达到优化的效果。我们是实现后可以进行性能测试的比对。
3、希尔排序的时间复杂度不好计算，需要进行推导，对导出来平均时间复杂度：O(N^1.3—N ^2)
4、稳定性：不稳定
1、基本思想
每次从待排序的数据元素中选出最大（或最小）的一个元素，存放子序列的起始位置，知道待排序的数据元素排完。实际上，我们可以一趟选出两个值，一个最大值一个最小值，然后将其放在序列开头和末尾，这样可以使选择排序的效率快一倍。
2、基本过程
代码实现：（此处是先选择最大的和最小的排在开头和结尾可以将效率提高一倍）
void SelectSort(int *arr, int n)
{
//参与单趟排序的第一个数和最后一个数的下标
int begin = 0, end = n - 1;
while (begin < end)
{
int max = begin;//max最大值的下标
int min = begin;//min最大值的下标
for (int i = begin; i <= end; ++i)
{
if (arr[i]>arr[max])
max = i;
if (arr[i] < arr[min])
min = i;
}
swap(&arr[min], &arr[begin]);//最小值放在开头
if (begin == max)//防止最大的数在begin位置被换走
max = min;
swap(&arr[max], &arr[end]);
++begin;
--end;
}
}
特性总结
直接选择排序思路非常好理解，但是效率不是很好，实际当中很少使用
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：不稳定
1、基本思想：将最大的数依次向后移动，第一趟下来最大的在最左边。
2、基本过程：
假设一共有M个元素需要排序，比较相邻的元素。如果第一个比第二个大（或小），则进行交换。
按照既定顺序，对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。第一轮比较完成以后，最后的元素应该会是整个元素列中最大（或最小）的数。
第N（N<M）轮比较结束后，会有N个元素已经被放置在正确的顺序位置，即每轮排序的最后一个元素，针对所有的剩余的元素（M-N）重复以上的步骤。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
图解
代码实现
void BubbleSort(int *arr, int n)
{
int end = n;
while (end)
{
int flag = 0;
for (int i = 1; i < end; ++i)
{
if (arr[i - 1]>arr[i])
{
swap(&arr[i], &arr[i - 1]);
flag = 1;
}
}
if(flag==0) break;
--end;
}
}
特性总结
快速排序是Hoare与1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素中的某元素作为基准值，按照该排序码将待排序集合分割成两个子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后对左右子序列重复这个过程，直到所有元素都排列在相应位置上为止。
将区间按照基准值划分为左右两半部分的常见、方式有：
1、基本过程
void QuickSort(int *arr, int begin, int end)
{
//若只存在一个数，则区间不存在
if (begin >= end)
return;
int left = begin, right = end-1;
int key = begin;
while (begin < end)
{
while (end>begin && arr[end] >= arr[key])
--end;
while (end>begin && arr[begin] <= arr[key])
++begin;
swap(&arr[begin], &arr[end]);
}
swap(&arr[end], &arr[key]);
key = end;
QuickSort(arr, left, key - 1);
QuickSort(arr, key + 1, right);
}
基本思路：
代码实现
void QuickSort1(int *arr, int begin, int end)
{
//若只存在一个数，则区间不存在
if (begin >= end)
return;
int left = begin, right = end;
int key = arr[begin];
while (begin < end)
{
while (end > begin && arr[end] >= key)
--end;//找小
arr[begin] = arr[end];//小的放左边的坑里
while (end > begin && arr[begin] <= key)
++begin;//找大
arr[end] = arr[begin];//大的放右边的坑里
}
arr[begin] = key;
int keyi = begin;
QuickSort1(arr, left, keyi - 1);
QuickSort1(arr, keyi + 1, right);
}
int PartSort(int *arr, int begin, int end)
{
int key = arr[begin];
while (begin < end)
{
while (key <= arr[end] && begin < end)
--end;
arr[begin] = arr[end];
while (key >= arr[begin] && begin < end)
++begin;
arr[end] = arr[begin];
}
arr[begin] = key;
int meeti = begin;
return meeti;
}
void QuickSort2(int *arr, int begin, int end)
{
stack<int>st;
st.push(end);
st.push(begin);
while (!st.empty())
{
int left = st.top();//左区间
st.pop();
int right = st.top();//右区间
st.pop();
int mid = PartSort(arr, left, right);
//当左区间>=mid-1则证明左区间已经排好序
if (left < mid - 1)
{
st.push(mid - 1);
st.push(left);
}
//当mid+1>=右区间则证明区间已将排好序
if (right>mid + 1)
{
st.push(right);
st.push(mid + 1);
}
}
}
基本思路
图解
代码实现
void QuickSort3(int *arr, int begin, int end)
{
if (begin >= end)
return;//防止区间不存在
int cur = begin, prev = begin - 1;
int key = end;
while (cur != key)
{
if (arr[cur] < arr[key] && ++prev != cur)
swap(&arr[cur], &arr[prev]);
++cur;
}
swap(&arr[++prev], &arr[key]);
key = prev;
QuickSort3(arr, begin, key - 1);
QuickSort3(arr, key + 1, end);
}
特性总结
堆排序可参见——堆排序详解