排序概论
一、什么是排序
排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。
1.可以分为 稳定/不稳定。
稳定：如果a=b,排序前，a就在b前面，排序后仍然a在b前面，就是稳定的。
2.可以分为：内排序/外排序。
内排序：所有排序操作都在内存中完成。
外排序:由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行。
排序耗时的操作：比较、移动。
二、排序算法分类
主要分为4大类：
交换类：冒泡、快排。特点：通过不断的比较和交换进行排序
选择类：简单选择、堆排序。特点：看准了再移动
插入类：简单插入、希尔排序。特点：通过插入的手段进行排序
归并类：归并排序。特点：先分割后合并
上述排序算法都是基于排序的，还有一类排序算法不是基于比较的排序算法，即计算排序、基数排序。
最开始排序算法都是O(n^2),希尔排序的出现打破僵局。
最基础的排序算法如下：
void simple_sort(int [] arr)
{
for(int i=0;i<arr.length-1;i++)
for(int j=i+1;j<arr.length;j++)
if(arr[i]>arr[j])
swap(arr,i,j);
}1234567
缺点：每次找最小值都是单纯的找，没有为下一次做出铺垫。
三、排序算法分析
1.冒泡排序
思想：两两相邻元素之间的比较，如果前者大于后者，就交换
void bubbleSort(int *a ,int n)
{
for(int i=0;i<n-1;i++)
for(int j=0;j<n-1-i;j++)
if(a[j]>a[j+1]) //如果前面的值大于后面的值，就交换，将最大值依次放到最后
swap(j,j+1);
}1234567
如原本序列基本是排好的，改进方法：定义一个变量，如果一次循环中没有交换过元素，则说明已经排好序。
void bubbleSort2(int * a,int n)
{
bool isChanged=true;
for(int i=0;i<n-1&&isChanged;i++)
{
isChanged=false;
for(int j=0;j<n-1-i;j++)
if(a[j]>a[j+1])
{
swap(j,j+1);
isChanged=true;
}
}
}1234567891011121314
复杂度分析：最好情况：n-1次比较后结束，时间O（n）,不占空间
最坏情况：n(n-1)/2;时间O(n^2),空间O(1).
2.简单选择排序
思想：每次循环找到最小值，并交换
相对于最简单的排序，对于很多不必要的交换做了改进，每个循环不断比较后记录最小值，只做了一次交换（当然也可能不交换，当最小值已经在正确位置）
for(int i=0;i<len-1;i++)
{
int min=i;
for(int j=i+1;j<len;j++)
{
if(a[min]>a[j])
min=j;
}
if(min!=i)
swap(a[min],a[i];
}1234567891011
最好：n(n-1)/2次比较 不交换 时间复杂度：o(n^2).
最坏：n(n-1)/2次比较 n-1次交换 复杂度仍为o(n^2).
3.简单插入排序
思想：给定序列，存在一个分界线，分界线的左边被认为是有序的，分界线的右边还没被排序，每次取没被排序的最左边一个和已排序的做比较，并插入到正确位置；我们默认索引0的子数组有序；每次循环将分界线右边的一个元素插入有序数组中，并将分界线向右移一位；
for(int i=1;i<len;i++)
{
int key=a[i]; //记录未排序的第一个值
int j=i-1; //未排序第一个值的左边
while(j>=0&&a[j]>key) //从右向左，找到合适地方插入
{
a[j+1]=a[j]; //将大值向后放置、腾出空间
j–;
}
a[j+1]=key; //最后将待插入的值放到合适位置上
} 1234567891011
最好：本身有序，只考虑前一次，进行n-1次比较，0次移动 时间O(n).
最坏：数组逆序，每次都要和前面的全部比较移动 时间复杂度：O(n^2).
排序中级阶段：（4个改进版的排序算法）
4.希尔排序
思想：简单插入排序的改进版。简单插入排序对数据少/基本有序时很有效，因此通过将序列进行分组排序使得每组容量变小，再进行分组排序，然后进行一次简单插入排序即可。分组是跳跃分组，逐渐缩小增量。按组进行插入排序操作，增量为1时，只需微调即可结束。
举例：例如增量increment=3;i%3相等的索引为一组，1 ，1+3,1+3*2：公式：increment=increment/3+1;
void shellSort(int * a,int len)
{
int h=1;
while(h<len)
h=3*h+1; //选取步长
while(h>0)
{
for(int j=h;j<len;j++)
{
int key=a[j]; //保存当前值
int i=j-h;
while(i>=0 && a[i]>key)
{
a[i+h]=a[i];
i=i-h; //当前分组中减去一个分量，继续往前
}
a[i+h]=key;
}
h=h/3; //步长依次减少
}
} 123456789101112131415161718192021
希尔排序的时间复杂度与选取的步长有关。
5.堆排序
思想：简单选择排序的改进版；构建一颗完全二叉树，首先构建大根堆，然后每次把根节点即最大值移除，并用编号最后的节点替代，这时数组长度减1，然后重新构建大根堆，以此类推
大根堆：任意父节点都比子节点大；
小根堆：任意父节点都比子节点小；
举例：构建一个小顶堆，得到的是一个降序序列
void adjustDown(int arr[],int i,int n)
//参数i:开始判断的非叶子节点 n：当前节点的最后一个数
{
int j=i2+1; //子节点
while(j<n)
{
if(j+1<n&&arr[j]>arr[j+1])//如果有右节点，而且右节点比左节点还小 (如果建立大根堆，改为<)
j++;
if(arr[i]<arr[j]) //(如果建立大根堆，改为>)
break; //如果最小的值就在顶上，直接退出，不进行交换操作
swap(arr[i],arr[j]); //交换i和j的值
i=j; //如果发生了换，要将底层节点作为新的头结点继续判断
j=i2+1; //如果j直接超过了根节点的个数n，证明无下层节点，直接返回
}
}
void makeHeap(int arr[] ,int n)
{
int i=0; //从非叶子节点开始找
for(i=n/2-1;i>=0;i–)
adjustDown(arr,i,n);
}
void heapSort(int arr[],int len)
{
int i=0;
makeHeap(arr,len);//第一步，构建初始堆 建堆复杂度为O(n).
for(int i=len-1;i>=0;i–)
{
swap(arr[i],arr[0]); // 交换堆顶元素和尾元素
adjustDown(arr,0,i); //重新建堆
}
}12345678910111213141516171819202122232425262728293031
6.归并排序
思想：利用递归进行分割和合并，分割直到长度为1为止，并在合并前保证两序列原本各自有序，合并后也有序；
void merge(int * a,int * b,int start,int mid,int end)
{
int i=start; //左边第一个开始
int j=mid+1; //右边第一个开始
int index=start; //结果的左边
while(i<=mid && j<=end)
{
if(a[i]<=a[j]) //如果左边的值小
b[index++]=a[i++];
else //右边的小，右边的往结果中放
b[index++]=a[j++];
}
//处理剩余元素
while(i<=mid)
b[index++]=a[i++];
while(j<=end)
b[index++]=b[j++];
}
void mergeSort(int * a,int b,int start,int end)
{
if(start<end) //如果区间还有元素
{
int mid=(end-start)/2+start; //找到中间元素
mergeSort(b,a,start,mid); //左边部分排序
mergeSort(b,a,mid+1,end); //右边部分排序
merge(a,b,start,mid,end); //合并操作
}
}
int main()
{
int arr[9]={5,3,1,7,9,6,2,4,8};
int temp_arr = new int [sizeof(arr)/sizeof(int)]; //创建临时数组b
memcpy(temp_arr ,a,sizeof(arr)); //临时数组b 存放的值和a的一样
merge_sort(arr,temp_arr,0,8); //执行排序算法
for(int i=0;i<sizeof(temp_arr)/sizeof(int);i++)
std::cout<<temp_arr[i]<<’ ';
return 0;
}1234567891011121314151617181920212223242526272829303132333435363738
时间复杂度为O(log2^n) 空间复杂度为O(n)
7.快速排序
思想：冒泡升级版，现阶段用最多。分治的策略，选取一个基准（一般将第一个作为基准），分为2部分，前半部分比其小，后半部分比其大，从后向前查找，将key值赋给中间值，然后分开2次调用该函数；
注意：如果序列基本有序或者序列个数较少，则可以采用简单插入排序，因为快速排序对于这些情况效率不高。
void quickSort(int a [] ,int low,int high)
{
if(low>=high)
return ;
int first=low;
int last=high;
int key=a[first];
while(first<last)
{
while(first<last && a[last]>=key)
--last;
a[first]=a[last];
while(first<last && a[first]<=key)
++first;
a[last]=a[first];
}
a[first]=key;
quickSort(a,low,first-1);
quickSort(a,first+1,high);
}
8.计数排序和基数排序
四、排序时间和空间复杂度总结