冒泡排序,简单选择排序，直接插入排序，希尔排序,堆排序，归并排序
1.冒泡排序
冒泡排序(BubbleSort)：冒泡排序是一种交换排序，它的基本思想是两两比较相邻的关键字，如果反序则交换，直到没有反序的记录为止。
1.我们先来看一个最简单的交换排序：它的思路是让每一个关键字都和它后面的关键字进行比较，如果大则交换，这样第一位置的关键字在一次循环后变成最小值。
void changeSort(int* p,int length)
{
if(p == nullptr)
{
return;
}
for(int i = 0 ; i < length - 1 ; i++)
{
for(int j = i + 1 ; j <= length - 1 ; j++)
{
if(p[i] > p[j])
{
swap(p[i],p[j]);
}
}
}
}
上面这段代码严格来说不算是标准的冒泡排序算法，因为它不满足“两两比较相邻记录”的思想。
2。正宗的冒泡排序算法：满足比较两两相邻的记录
void swap(int& a,int& b)
{
int temp = a;
a = b;
b = temp;
}
void bubbleSort(int* p,int length)
{
if(p == nullptr)
{
return;
}
for(int i = 0 ; i < length - 1 ; i++)
{
//从后往前循环
for(int j = length - 2 ; j >= i ; j--)
{
if(p[j] > p[j+1])
{
swap(p[j],p[j+1]);
}
}
}
}
3。上面的冒泡排序算法也是可以改进的。必如说我们的待排序列是{2，1，3，4，5，6，7，8，9}，很显然只需要第一关键字和第二关键字交换后待排序列就达到了有序。然而在正宗的冒泡排序算法中，i = 1到7以及每个for循环中的j循环都执行了一遍。也就是我们做了没有必要的比较工作。我们应当在i=1循环中发现没有数据交换就退出循环，因为没有数据交换表明是有序的。改进的冒泡排序算法如下：
void swap(int& a,int& b)
{
int temp = a;
a = b;
b = temp;
}
void bubbleSort(int* p,int length)
{
if(p == nullptr)
{
return;
}
bool flag = true; //标记循环是否继续的变量
for(int i = 0 ; i < length - 1 && flag; i++)
{
flag = false;
for(int j = length - 2 ; j >= i ; j--)
{
if(p[j] > p[j+1])
{
swap(p[j],p[j+1]);
flag = true; //上一轮循环有数据交换那么下一轮循环继续
}
}
}
}
冒泡排序的时间复杂度：最坏的情况显然是对一个逆序的待排序列排序，此时比较次数为Sn=1+2+3+...+n-2+n-1 = nn/2 - n/2,根据大O阶推导法可得时间复杂度为O(nn).
2.简单选择排序
简单选择排序(SImpleSelectSort)：就是通过n-i-1次关键字间的比较，从n-i-1个记录中选出关键字最小的记录并和第i（0 =< i =< n-1）个记录交换。
简单选择排序算法如下：
void swap(int& a,int& b)
{
int temp = a;
a = b;
b = temp;
}
void simpleSelectSort(int* p,int length)
{
if(p == nullptr)
{
return;
}
int min = 0; //存储i号位置的最小值
for(int i = 0 ; i < length - 1 ; i++)
{
min = i; //假设i号位置就为最小值
for(int j = i + 1 ; j <= length - 1 ; j++)
{
if(p[j] < p[min]) //i号位置的元素与length-i-1号个元素比较
{
min = j;
}
}
//表示在length-i-1个元素种找到最小值然后交换
if(min != i)
{
swap(p[min],p[i]);
}
}
}
简单选择排序的时间复杂度：最坏的情况显然是对一个逆序的待排序列排序，第i躺排序需要n-i次关键字比较，此时比较次数为Sn=1+2+3+...+n-2+n-1 = nn/2 - n/2,根据大O阶推导法可得时间复杂度为O(nn).和冒泡排序算法的时间复杂度是一样的。但是简单选择排序的性能率优于冒泡排序。
3.直接插入排序算法
直接插入排序(StraightInsertSort)：将一个记录插入到已经排好序的有序表，从而得到一个新的，记录数加一的有序表。
直接插入排序算法的简单实现：
void straightInsertSort(int* p,int length)
{
if(p == nullptr)
{
return;
}
//假设一号位置已经排好序
for(int i = 2 ; i <= length - 1 ; i++)
{
//将i号位置的元素插入到有序序列中
if(p[i-1] > p[i])
{
p[0] = p[i]; //在0号位置设置哨兵
int j = 0;
for(j = i - 1 ; p[j] > p[0] ; j--)
{
p[j+1] = p[j];
}
p[j+1] = p[0];
}
}
}
直接插入排序的时间复杂度：本算法的时间复杂度也为O(n*n)。
当待排序列的记录本身就是基本有序的或者记录数较少时，直接插入排序算法是比较高效地。
上述三个内排序的时间复杂度都为O(n * n).那么有没有时间复杂度超越O(n*n)的内排序算法呢？当然有的呢。
4.希尔排序
希尔排序(ShellSort)：希尔排序算法是于1959年由希尔科学家提出来的一个算法，是一种对直接插入排序算法改进后时间复杂度达到O(n3/2)的算法。
如何让待排序的记录个数较少呢？就是将原本有大量记录数的记录进行分组。分割成若干个子序列，此时每个子序列待排序列的记录数就少了，然后再这些子序列分别进行直接插入排序，当整个序列基本有序时，再对全体记录进行一次直接插入排序。我们采取跳跃分割的策略：将相距某个增量的记录组成一个子序列，这样才能保证再子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。
希尔排序的简单实现：
void shellSort(int* p,int length)
{
if(p == nullptr)
{
return;
}
int increment = length - 1; //有一个位置作为哨兵
do
{
increment = increment / 3 + 1; //增量序列，目前选取增量方法未确定
for(int i = increment + 1 ; i <= length ; i++)
{
if(p[i] < p[i-increment])
{
p[0] = p[i]; //0号位置作为哨兵存储最小值
int j = 0;
for(j = i - increment ; j > 0 && p[j] > p[0] ; j -= increment)
{
p[j+increment] = p[j];
}
p[j+increment] = p[0];
}
}
}
while(increment > 1);
}
上诉算法种对于增量的选取是increment = increment / 3 + 1;但是对于选取什么样的增量最好，迄今为止还没有人找到最好的增量序列。但是呢，增量序列的最后一个值必须等于1才行，因为当整个序列基本有序时需要对全体记录进行一次直接插入排序。
记录是跳跃式的移动，所以本算法是一个不稳定的内部排序，其时间复杂度为O(n3/2).
5.堆排序
在讲堆排序之前，我们先了解堆这种数据结构。
堆：堆是具有下列性质的完全二叉树。堆分为大顶堆和小顶堆。
大顶堆：每个结点的值都大于或者等于其左右孩子节点的值。
小顶堆：每个节点的值都小于或者等于其左右孩子结点的值。
比如说下图：
大顶堆.png
小顶堆.png
堆排序(HeapSort)：将待排序序列构造成大顶堆或者小顶堆。此时整个序列的最大值或者最小值就是堆顶根节点。因为堆是一颗完全二叉树，所以采用顺序存储结构存储。将它移走（其实就是将其与堆数组的末尾元素交换），然后将剩余的n-1个序列重新构造成一个堆，这样就得到n个元素的次小值或者次大值。堆排序是对于简单选择排序的改进。
假设我们要对一个长度为n的待排序列从大到小进行排序。构建大顶堆的过程其实就是将每一个非叶子节点当作根节点，将其和其子树构建成大顶堆。依据二叉树的性质度为2的结点（非叶子节点）和度0的结点满足：n = d2 + d0；d2 + 1 = d0.所以在计算中非叶子节点可用d2 = n/2来表示;也就是说，如果用一个数组存储n个结点的完全二叉树，那么n/2长度存储的是非叶子节点。
堆排序算法的简单实现：
//从下标0开始
void heapSort(int* p,int length)
{
if(p == nullptr)
{
return;
}
//将一个无序序列构建成大顶堆
for(int i = (length / 2) - 1 ; i >= 0 ; i--)
{
heapAdjust(p,i,length);
}
//数组尾部元素即为大顶堆的根节点元素
for(int i = length - 1 ; i > 0 ; i--)
{
swap(p[0],p[i]);
//在length - 1个元素中重新调整大顶堆
heapAdjust(p,0,i);
}
}
void heapAdjust(int* p,int i,int length)
{
int temp = p[i];
for(int j = 2*i ; j <= length - 2 ; j *= 2)
{
//左孩子结点小于右孩子
if(p[j] < p[j+1] && j < length -1)
{
j++;
}
//根节点大于左孩子或者右孩子则当前结点值可以为子树大顶堆根节点
if(temp >= p[j] )
{
break;
}
//交换根节点与子树种结点较大的值
p[i] = p[j];
i = j;
}
p[i] = temp;
}
void swap(int& a,int& b)
{
int temp = a;
a = b;
b = temp;
}
堆排序算法的时间复杂度：在初始构建堆的过程中，因为我们是从完全二叉树最下层最右边的非终端结点开始构建，将他与其孩子进行比较和互换操作，对于每个非终端结点来说，最多进行两次比较和互换操作，所以初始化构建堆的时间复杂度为O(n/2*2) = O(n)。在正式排序时，第i次取堆顶记录重建堆需要log(n)的时间，因为完全二叉树的某个节点到根节点的距离为log2i+1.，并且需要取n-1次堆顶记录，所以重建堆的时间复杂度为O(n * logn)。
注意由于初始构建堆所需的比较次数较多，所以它并不适合待排序列序列个数较少的情况。
6.归并排序
归并排序(MergingSort)：假设初始序列有n个记录，则可以看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2（n/2为不小于n/2的最小整数）个长度为2或者为1的有序子序列。再两两归并如此重复直到得到一个长度为n的有序序列。这种排序方法也叫做二路归并排序法。
归并排序的递归实现：
/*
* @param merge_array存储两个有序子序列归并后的结果数组
* @param first为第一个子序列的首元素下标，middle为第一个子序列的尾元素下标，end为第二个有序子序列尾元素的下标
*/
void merge(int merge_array[], int first, int middle, int end)
{
//分配两段连续空间分别存储[first,middle],[middle+1,end]的两个子序列。
int left_num = middle - first + 1;
int right_num = end - middle;
int* left_array = new int[left_num];
int* right_array = new int[right_num];
memset(left_array,0,sizeof(int) * left_num);
memset(right_array, 0, sizeof(int) * right_num);
//归并前初始化两个子序列
for (int i = first, j = 0; i <= middle; ++i, ++j)
left_array[j] = merge_array[i];
for (int i = middle + 1, j = 0; i <= end; ++i, ++j)
right_array[j] = merge_array[i];
//将两个子序列归并入merge_array中
for (int key = first, left_index = 0, right_index = 0; key <= end; ++key)
{
if (left_index == left_num)
{
while (key <= end)
merge_array[key++] = right_array[right_index++];
break;
}
else if (right_index == right_num)
{
while (key <= end)
merge_array[key++] = left_array[left_index++];
break;
}
else
{
if (left_array[left_index] < right_array[right_index])
merge_array[key] = left_array[left_index++];
else
merge_array[key] = right_array[right_index++];
}
}
delete[]left_array;
delete[]right_array;
}
/*
* @param merge_array为待排序数组，first为数组首元素下标，end为尾元素下标
*/
void merge_sort(int merge_array[], int first, int end)
{
if (first < end)
{
int middle = (first + end) / 2;
merge_sort(merge_array, first, middle);
merge_sort(merge_array, middle + 1, end);
merge(merge_array, first, middle, end);
}
}
上述算法的时间复杂度为O(n*logn).虽然递归排序比较占用内存，但是归并排序是一种稳定的算法。
7.快速排序
快速排序(QuickSort)：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
对待排序列进行快速排序的算法步骤：
说明步骤之前先说明一个概念：什么是枢轴呢？枢轴（pivot）：我们需要在待排序列中找到一个位置对应的关键字，使得它左边的关键字都比它小，右边的关键字都比它大。这样的关键字称为枢轴。
步骤：
1.找出待待排序列中的枢轴值。
2.对枢轴值左边的值构成的子序列重复第一步骤递归排序。
3.对枢轴值右边的值构成的子序列重复第一步骤递归排序。
找出待排序列中的枢轴值如下：
/*
* @brief 找出一段序列中的枢轴值,快速排序核心
* @parame p为待排序列,low为待排序列的起点下标,high为待排序列的末尾下标
*/
int getPivot(int** p, int low, int high)
{
int pivotKey = (*p)[low]; //将待排序列的第一个元素作为枢轴值
while (low < high)
{
while (low < high && (*p)[high] >= pivotKey)
{
high--;
}
swap(p, low, high);
while (low < high && (*p)[low] <= pivotKey)
{
low++;
}
swap(p, low, high);
}
return low;
}
快速排序的简单实现如下：
void swap(int**& p, int index1, int index2)
{
int temp = (*p)[index1];
(*p)[index1] = (*p)[index2];
(*p)[index2] = temp;
}
/*
* @brief 找出一段序列中的枢轴值,快速排序核心
* @parame p为待排序列,low为待排序列的起点下标,high为待排序列的末尾下标
*/
int getPivot(int** p, int low, int high)
{
int pivotKey = (*p)[low]; //将待排序列的第一个元素作为枢轴值
while (low < high)
{
while (low < high && (*p)[high] >= pivotKey)
{
high--;
}
swap(p, low, high);
while (low < high && (*p)[low] <= pivotKey)
{
low++;
}
swap(p, low, high);
}
return low;
}
/*
* @param p为待排序列,low为待排序列的起点下标,high为待排序列的末尾下标
*/
void quickSort(int* p, int low, int high)
{
if (p == nullptr)
{
return;
}
int pivot;
if (low < high)
{
pivot = getPivot(&p, low, high);
quickSort(p, low, pivot - 1);
quickSort(p, pivot + 1, high);
}
}
上述算法时间复杂度为O(n*n)。本算法的时间复杂度推导比较麻烦就不推到了。
快速排序算法的优化：
1.优化选取枢轴
2.优化不必要的交换
3.优化小数组的排序方案
4.优化递归操作
由于关键字的比较和交换是跳跃的，所以快速排序算法也是一种不稳定的排序算法。
8.总结
各大算法有利也有弊，我们应当根据场合来选择适当的排序算法。
各种排序算法的优缺点.png
