8种排序算法
-
【排序算法的稳定性】
指的是对于两个相同的元素（比如数组中的相同数字），若排序后两个元素的前后位置不发生改变，则说这种排序算法是稳定的，若改变则是不稳定的。
不稳定的，会导致排序可能结果不唯一，比如用来排序的关键字是结点中的整型元素，虽然遇到两个整型元素相同，但是结点中其他元素不相同，此时两个结点的前后位置发生改变就会导致所有结点的排序结果可能不唯一。
简单说，需要两两相邻比较的都是稳定的，会跳跃比较的都是不稳定的。 -
【内排序与外排序】
内排序是指排序过程中，所有排序记录都全部放置在内存中。（栈内存或堆内存）
外排序是指排序记录太多时，内存放不下，整个排序过程中需要进行内存和外部硬盘存储之间的多次数据交换才能进行。
此处8大排序算法都是内排序。
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
【算法】【平均时间复杂度】【最好时】【最坏时】【空间复】【稳定性】
——————————————————————————————————————
【冒泡排序】----------【n^2】 【n】----------【n^2】--------【1】---【稳定】
【简单选择排序】----【n^2】 【n^2】------【n^2】---------【1】---【稳定】
【直接插入排序】----【n^2】 【n】----------【n^2】--------【1】---【稳定】
【希尔排序】-【nlogn~n^2】 【n^1.5】----【n^2】--------【1】-【不稳定】
【堆排序】----------【nlogn】 【nlogn】---【nlogn】-------【1】-【不稳定】
【归并排序】-------【nlogn】 【nlogn】---【nlogn】-------【n】---【稳定】
【快速排序】-------【nlogn】 【nlogn】-----【n^2】----【logn~n】【不稳定】
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
- 【8大排序算法简单介绍】
【冒泡排序】两层for循环，排序n-1趟，每趟将一个最大的数冒泡到最后。比较相邻两个元素，如果反序则交换，直到没有反序记录为止。缺点，要频繁交换。优化点：使用一个flag标记，若不再发生交换，说明剩余的序列已经全部有序，不用再进行后面的排序过程了。最好是时间复杂度为n，即已经排好序的。鸡尾酒排序——双向冒泡排序，奇数轮从左到右冒泡排序，偶数轮从右到左冒泡排序，这样可以优化类似2,3,4,5,6,7,8,1这样的基本有序序列。如果用普通冒泡排序需要进行7轮。而双向冒泡只需要进行3轮，当然，这种基本有序的最好使用直接插入排序更佳。
【简单选择排序】两层for循环，每一轮先“简单选择”第一个数当做min然后和后面的数比较，若遇到更小的就互换下标位置，每轮都找到最小元素后再交换值，特点就是交换数据次数少。最好最差时间复杂度都是n^2，即必须完成两个for循环的比较，不能提前结束，即使是已经排好序。
【直接插入排序】两层for循环，先认为前i个元素有序，将第j=i+1个插入，依次从后向前和前i个数比较，遇到比他大的就交换（此处可优化为先用临时空间记录当前值，然后所有元素后移结束后再替换回去，减少交换次数），遇到小的就说明有序可以退出了。在数据量少和数据基本有序时效果很好。最好的时间复杂度是n，不用移动数据，每次加到最后面就行了。
【希尔排序】又叫缩小增量排序，先将序列分成多个子序列，子序列数据量变少，适用于直接插入排序。然后缩小增量，分成更多子序列再直接插入排序得到基本有序的序列，当最后增量为1时，最后进行一次直接插入排序，因为序列已经基本有序，所以可以很快排好。跳跃式地分成子序列然后再将子序列使用直接插入排序法。根据增量从n/3+1减到1结束while循环排序。
【堆排序】也是将一个数组序列进行排序，不是对树进行排序。这个数组是由完全二叉树的广度遍历得到的。要得到节点i比其左子节点2i+1和右子节点2i+2都大。重点是堆调整函数，该函数时间复杂度为logn。先将n数组构造成一个大顶堆（需要调用n/2次堆调整函数，故这块时间复杂度为n/2*logn）；然后将堆顶最大元素与末尾元素交换，就排好了最大数，然后从首节点向下调整和左右子节点的位置来调整前面n-1个元素的堆（需要选择出n次堆顶元素，并调用n次堆调整函数，故这块时间复杂度为n*logn）。因此总的时间复杂度应该是：n/2*logn+n*logn约为n*logn。最好最差都要进行所有的比较调整过程，故时间复杂度一样为n*logn。
【归并排序】分治法，均分。方法一：使用递归将一个序列先逐步对半拆分到一个个元素，然后再使用merge函数两两排序后合并，直到合并到序列原长结束。方法二：使用循环迭代代替递归，可节省logn的递归空间，时间效率也有提高。将相邻的长为K(从1开始循环到n/2)的两个子序列合并成2K存入临时数组，然后再从临时数组将相邻的2K合并到原数组中，合并过程中有排序。最终合并到原长的序列就是排好序的。
时间复杂度：一趟归并需要遍历一遍元素故时间为n，有完全二叉树的深度可知要归并logn次，因此总的时间复杂度为n*logn，且最好和最坏都一样。
【快速排序】分治法，不一定均分。首先要有一个getPivot()函数（或partition()），从原序列中选出大小尽量偏中间的一个数作为枢轴值pivotkey并移到序列位置1(位置0存放拷贝值)，然后从原序列两头用两根指针(两辆马车)先尾后头分别往中间遍历并和枢轴值比较然后替换首尾，在两根指针相遇时得到由pivotkey大致瓜分的左右两部分并返回pivot位置，然后对两部分再次递归。每次返回pivot位置后，将数组首位与该位置的值替换，则固定了一个元素的位置，可见要如此循环n次getPivot()函数才能固定所有元素位置。每个getPivot()函数内部交换元素位置的时间复杂度为logn。因此总的时间复杂度为n*logn，此为平均和最好。最差情况是pivotkey选择的都是边界值，导致分治不均，每次都要遍历n个元素才能确定一个pivot位置，因此最差的是n^2。
【基数排序——又叫桶排序】
算法思想：是将序列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间（O(n)）。但桶排序并不是比较排序，他不受到 O(n log n) 下限的影响。
简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的在进行排序。
例如要对大小为[1..1000]范围内的n个整数A[1..n]排序：
首先，可以把桶设为大小为10的范围，具体而言，设集合B[1]存储[1..10]的整数，集合B[2]存储 (10..20]的整数，…集合B[i]存储((i-1)*10， i*10]的整数，i=1，2..100。总共有 100个桶。然后，对A[1..n]从头到尾扫描一遍，把每个A[i]除以桶子数10放入对应的桶B[j]中。 再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任何排序法都可以。最后，依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这样就得到所有数字排好序的一个序列了。
假设有n个数字，有m个桶，如果数字是平均分布的，则每个桶里面平均有n/m个数字。如果对每个桶中的数字采用快速排序，那么整个算法的复杂度是
O(n + m * n/m*log(n/m)) = O(n + nlogn – nlogm)
从上式看出，当m接近n的时候，桶排序复杂度接近O(n)
当然，以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的 ，实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中，那就退化成一般的排序了。
前面说的几大排序算法 ，大部分时间复杂度都是O(n2)，也有部分排序算法时间复杂度是O(nlogn)。而桶式排序却能实现O(n)的时间复杂度。但桶排序的缺点是：
1）首先是空间复杂度比较高，需要的额外开销大。排序有两个数组的空间开销，一个存放待排序数组，一个就是所谓的桶，比如待排序值是从0到m-1，那就需要m个桶，这个桶数组就要至少m个空间。
2）其次待排序的元素都要在一定的范围内等等。
- 【排序算法分类：】
插入排序：直接插入排序，希尔排序（增量插入排序）
选择排序：简单选择排序，堆排序（每次选出堆顶元素作为最值）
交换类排序：冒泡排序，快速排序
引入辅助空间的排序：归并排序（在归并两个长为n/2的子序列时，使用了长为n的辅助数组空间）
#include<iostream>
using namespace std;
void swap(int &a, int& b)
{
int temp = a;
a = b;
b = temp;
}
//1、冒泡排序法(从小到大)，排序n-1趟，每趟将一个最大的数冒泡到最后。
//优化点：使用一个flag标记，若不再发生交换，说明剩余的序列已经全部有序，不用再进行后面的排序过程了。
void bubbleSort(int arr[], int n)
{
if (arr && n)
{
//若flag=1则还有必要继续比较进行排序，否则说明已经全部有序。
int flag = 1;
//排序n-1趟
for (int i = 0; i < n - 1 && flag; i++)
{
flag = 0;
for (int j = 0; j < n - i - 1; j++)
{
if (arr[j]>arr[j + 1])
{
swap(arr[j], arr[j + 1]); //缺点就是要频繁地替换
flag = 1;
}
}
}
}
}
//2、简单选择排序法，每次选择当前数为最小数，与后面的比较若有更小的则交换
//优化点：每次比较后只替换更小的位置标记，而不进行实际的元素替换，当最后找到最小的再替换，可以减少替换次数。
void selectSort(int arr[], int n)
{
if (arr && n)
{
//选择n-1次当前最小值
for (int i = 0; i < n - 1; i++)
{
int min = i;
for (int j = i + 1; j < n; j++)
{
//与后面的比较若有更小的则先标记,直到标记出最小的
if (arr[j] < arr[min])
{
min = j;
}
}
swap(arr[i], arr[min]);
}
}
}
//3、直接插入排序，先将第一个当成有序，再将第二个插入，再将前两个当成有序，第三个插入。。。
//更适用的场合：序列基本有序，则插入时可以移动更少的数据；数据量比较少，移动数据的次数也就少了。
void insertSort(int arr[], int n)
{
if (arr && n)
{
for (int i = 0; i < n-1; i++)
{
//认为前i个元素有序，将第i+1个插入，依次从后向前和前i个数比较，
//遇到比他大的就交换，遇到小的就说明有序可以退出了
for (int j = i+1; j > 0; j--)
{
if (arr[j-1] > arr[j])
{
swap(arr[j-1], arr[j]);
}
else
{
//遇到小的就说明有序可以退出了
break;
}
}
}
}
}
//4、希尔排序，又叫缩小增量排序，先将序列分成多个子序列
//子序列数据量变少，适用于直接插入排序。然后缩小增量，分成更多子序列再直接插入排序得到基本有序的序列
//当最后增量为1时，最后进行一次直接插入排序，因为序列已经基本有序，所以可以很快排好。
void shellSort(int arr[], int n)
{
int increment = n;
//缩小增量到1时，相邻比较，最后一趟排序
while (increment > 1)
{
increment = increment / 3 + 1; //增量递减规则可以自己设置，只要能最终减到1
//内部对子序列进行直接插入排序。当increment为1时，和上面的直接插入排序代码一样
for (int i = 0; i < n - increment; i++)
{
for (int j = i+increment; j > 0; j-=increment)
{
//前面的比后面的大则要交换
if (arr[j - increment] > arr[j])
{
swap(arr[j - increment], arr[j]);
}else
{
//遇到小的就说明有序可以退出了
break;
}
}
}
}
}
//5、堆排序，也是将一个数组序列进行排序，不是对树进行排序。这个数组是由完全二叉树的广度遍历得到的。
//要得到节点i比其左子节点2i+1和右子节点2i+2都大。
//先将n数组构造成一个大顶堆，然后将堆顶最大元素与末尾元素交换，就排好了最大数，
//然后调整前面n-1个元素的堆。从每个s节点向下调整和左右子节点的位置
void heapAdjustDown(int arr[], int s, int len)
{
int i = 2 * s + 1; //i为s节点的左孩子节点
for (; i < len; i = 2 * s + 1)
{
if (i + 1 < len && arr[i] < arr[i + 1])
{
//左右孩子中，右子节点更大，用来替换s节点
++i;
}
if (arr[s] >= arr[i])
{
//说明不用替换，当前节点s就是3个节点中最大的
break;
}
//需要和子节点替换
swap(arr[s], arr[i]);
//i节点即为更小的节点，接下来需要判断它和左右孩子的关系。接着循环
s = i;
}
}
//具体排序函数
void heapSort(int arr[], int len)
{
if (arr && len)
{
//先将数组构造成大顶堆，循环从后面的节点将大的节点往前调整
for (int i = (len - 1) / 2; i >= 0; i--)
{
heapAdjustDown(arr, i, len);
}
//再循环将大顶堆的堆顶元素换位到数组后面，从而得到从小到达的序列。
//每次换位后，需要从节点0重新调整堆，将小数逐渐下移
for (int i = len - 1; i > 0; i--)
{
swap(arr[0], arr[i]);
heapAdjustDown(arr, 0, i);
}
}
}
//6、归并排序
//方法一：使用递归，会多用到logn的栈内存和长为n的临时辅助数组空间
//方法二：使用循环迭代，会多用到长为n的临时辅助数组空间
//7、快速排序，先选择一个轴心数（换到第一个位置），左右两根指针分别向中间移动（和轴心数比较后互换），
//相遇时确定轴心数位置，并分为左右两子序列，再递归快速排序子序列
int getPivot(int arr[], int start, int end)
{
int pivot; //轴心位置
int p1 = start, p2 = end + 1; //两根指针
//先从三个数中将大小在中间的数换到第一个位置
int mid = (start + end) / 2;
if (arr[end] < arr[mid])
{
swap(arr[end], arr[mid]); //使end位置元素更大
}
if (arr[end] < arr[start])
{
swap(arr[start], arr[end]); //使end位置元素最大
}
if (arr[start] < arr[mid])
{
swap(arr[start], arr[mid]); //成功将中间数换到start位置
}
int pivot_value = arr[start]; //轴心值
while (1)
{
do
{
p1++; //从初始位置的轴心数后一个开始先右移，直到遇到比轴心值大的要换到轴心右边
} while (arr[p1] < pivot_value && p1 < end);
do
{
p2--; //从end+1处自减到end开始先左移，直到遇到比轴心值小的要换到轴心左边
} while (arr[p2] > pivot_value && p2 > start);
if (p1<p2)
{
swap(arr[p1], arr[p2]);
}
else
{
break; //p1>=p2时退出，此时将p2作为轴心数的位置
}
}
pivot = p2;
return pivot;
}
void quickSort(int arr[], int start, int end)
{
if (arr && end > start)
{
int pivot = getPivot(arr, start, end);
swap(arr[start], arr[pivot]);
//递归排序左子序列
quickSort(arr, start, pivot - 1);
//递归排序右子序列
quickSort(arr, pivot + 1, end);
}
}
//快速排序在递归子序列长度够小时，转为其他的简单排序更快，如直接插入排序
void quickSort1(int arr[], int start, int end)
{
if (arr && end > start)
{
if (end - start > 4)
{
int pivot = getPivot(arr, start, end);
swap(arr[start], arr[pivot]);
//递归排序左子序列
quickSort1(arr, start, pivot - 1);
//递归排序右子序列
quickSort1(arr, pivot + 1, end);
}
else //用直接插入排序
{
insertSort(arr + start, end - start + 1);
}
}
}
int main()
{
int arr1[10] = { 1, 4, 0, 7, 2, 5, 8, 3, 6, 9 };
for (int i = 0; i < 10; i++)
{
cout << arr1[i] << " ";
}
cout << endl << "冒泡排序后：" << endl;
bubbleSort(arr1, 10);
for (int i = 0; i < 10; i++)
{
cout << arr1[i] << " ";
}
cout << endl;
int arr2[10] = { 1, 4, 0, 7, 2, 5, 8, 3, 6, 9 };
cout << endl << "简单选择排序后：" << endl;
selectSort(arr2, 10);
for (int i = 0; i < 10; i++)
{
cout << arr2[i] << " ";
}
cout << endl;
int arr3[10] = { 1, 4, 0, 7, 2, 5, 8, 3, 6, 9 };
cout << endl << "直接插入排序后：" << endl;
insertSort(arr3, 10);
for (int i = 0; i < 10; i++)
{
cout << arr3[i] << " ";
}
cout << endl;
int arr4[10] = { 1, 4, 0, 7, 2, 5, 8, 3, 6, 9 };
cout << endl << "希尔排序后：" << endl;
shellSort(arr4, 10);
for (int i = 0; i < 10; i++)
{
cout << arr4[i] << " ";
}
cout << endl;
int arr5[10] = { 1, 4, 0, 7, 2, 5, 8, 3, 6, 9 };
cout << endl << "堆排序后：" << endl;
heapSort(arr5, 10);
for (int i = 0; i < 10; i++)
{
cout << arr5[i] << " ";
}
cout << endl;
int arr6[10] = { 1, 4, 0, 7, 2, 5, 8, 3, 6, 9 };
cout << endl << "快速排序后：" << endl;
quickSort(arr6, 0, 9);
for (int i = 0; i < 10; i++)
{
cout << arr6[i] << " ";
}
cout << endl;
int arr61[10] = { 1, 4, 0, 7, 2, 5, 8, 3, 6, 9 };
cout << endl << "快速+直接插入排序后：" << endl;
quickSort1(arr61, 0, 9);
for (int i = 0; i < 10; i++)
{
cout << arr61[i] << " ";
}
cout << endl;
}
