排序算法总结（C++）
算法复杂度
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
一：冒泡排序
经典的排序算法，通过依次比较相邻两个元素之间的大小，从头比较到尾，相当于一个水泡从下面一直往上，故而称为冒泡排序。
步骤：1.比较两个相邻元素的大小，如果比它大（小），就将其交换。
2.从下标0开始扫描，一直扫描到尾部，每次比较都将最大（小）的交换至最后。
3.继续比较，重复上述过程。
代码：
void Bubble Sort(int *arr,int len)
{
for(int i=0;i<len-1;++i) //比较的次数
{
for(int j=0;j<len-i-1;++j)
{
if(arr[j]>arr[j+1])
swap(arr[j],arr[j+1]);
}
}
}二：选择排序
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
步骤：
1.先进行第一次比较，找出数组最大（小）的元素，将其放在第一位，目前已知第一位是最大（小）的元素。
2.从第二个下标位置开始，找出剩余数组中最大（小）的元素，放在第二位。
3.继续重复寻找，直到将其全部排序
代码：
void Select Sort(int *arr,int len)
{
int temp;
for(int i=0;i<len-1;++i)
{
temp=i;
for(int j=i+1;j<len;++j)
{
if(arr[j]>arr[j+1])
temp=j;
}
swap(arr[i],arr[temp]);
}
}三：插入排序
插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
步骤：
1.首先认为第一个元素是已经排序好的，那么从第二个元素开始，如果比第一个小，那么就将其排在第一位，第一个元素后移。
2.同样，继续从第三个开始，从已经排序好的后面开始比较，如果比第二个小，就与第一个比较，元素依次后移。
3.对后面的元素重复操作，一直到比较完成。
代码：
void Insert Sort(int *arr,int len)
{
int temp;
for(int i=1;i<len;++i)
{
int j=i-1;
temp=arr[i];
while(j>=0 && temp>arr[j])
{
arr[j+1]=arr[j];
--j;
}
arr[j+1]=temp;
}
}四：希尔排序
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。
代码：
void shellsort1(int a[], int n)
{
int i, j, gap;
for (gap = n / 2; gap > 0; gap /= 2) //步长
for (i = 0; i < gap; i++) //直接插入排序
{
for (j = i + gap; j < n; j += gap)
if (a[j] < a[j - gap])
{
int temp = a[j];
int k = j - gap;
while (k >= 0 && a[k] > temp)
{
a[k + gap] = a[k];
k -= gap;
}
a[k + gap] = temp;
}
}
}
但这种略显复杂，稍做优化
void shellsort2(int a[], int n)
{
int j, gap;
for (gap = n / 2; gap > 0; gap /= 2)
for (j = gap; j < n; j++)//从数组第gap个元素开始
if (a[j] < a[j - gap])//每个元素与自己组内的数据进行直接插入排序
{
int temp = a[j];
int k = j - gap;
while (k >= 0 && a[k] > temp)
{
a[k + gap] = a[k];
k -= gap;
}
a[k + gap] = temp;
}
}
五：归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
- 把长度为n的输入序列分成两个长度为n/2的子序列；
- 对这两个子序列分别采用归并排序；
- 将两个排序好的子序列合并成一个最终的排序序列。
//将有二个有序数列a[first...mid]和a[mid...last]合并。
void mergearray(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
while (i <= m && j <= n)
{
if (a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (i = 0; i < k; i++)
a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last, int temp[])
{
if (first < last)
{
int mid = (first + last) / 2;
mergesort(a, first, mid, temp); //左边有序
mergesort(a, mid + 1, last, temp); //右边有序
mergearray(a, first, mid, last, temp); //再将二个有序数列合并
}
}
bool MergeSort(int a[], int n)
{
int *p = new int[n];
if (p == NULL)
return false;
mergesort(a, 0, n - 1, p);
delete[] p;
return true;
}
六：快速排序
想必用的最多的就是快排了吧，用sort用得不亦乐乎。好吧，回归正话。
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
步骤为：
- 从数列中挑出一个元素，称为“基准”（pivot），
- 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int Partion(int *arr,int low,int high)
{
int temp=arr[low];
while(low<high)
{
while(low<high && arr[high]>=temp)
--high;
swap(arr[low],arr[high]);
//arr[low]=arr[high];
while(low<high && arr[low]<=temp)
++low;
swap(arr[low],arr[high]);
//arr[high]=arr[low];
}
return low;
}
void quicksort(int *arr,int low,int high)
{
if(low<high)
{
int t=Partion(arr,low,high);
quicksort(arr,low,t-1);
quicksort(arr,t+1,high);
}
}
int main()
{
int a[5];
for(int i=0;i<5;++i)
scanf("%d",&a[i]);
quicksort(a,0,4);
printf("%d %d %d %d %d",a[0],a[1],a[2],a[3],a[4]);
return 0;
}
待更新……
（PS：本期部分素材来源于https://www.cnblogs.com/onepixel/articles/7674659.html）