一、冒泡排序算法
1. 冒泡排序算法分析
冒泡排序：Bubble sort，也叫做起泡排序，是一种交换性质的排序，基本思想是相邻两条记录进行比较，不符合规则就交换，符合规则不交换。冒泡排序的具体步骤描述如下
第一趟排序：
第1个元素与第2个元素比较，如果第1个元素大于第2个元素则交换，否则不进行任何操作；第2个元素与第3个元素比较，如果第2个元素大于第3个元素，则交换两个元素，否则不进行任何操作；重复上面操作，两两比较直到第n-1个元素和第n个元素比较完毕，第一趟冒泡结束。
经过第一趟排序后，整个数列中最大的数，通过冒泡冒到了数列的最后一个位置。
第二趟排序：
对前n-1个元素进行冒泡排序，即第1个位置与第2个位置比较，大于则交换，否则无操作；一直到第n-2个位置和第n-1个位置比较，大于则交换，否则无操作。通过第二趟冒泡排序，前n-1个元素中最大的数冒泡到n-1位置，也就是原始数组的倒数第二个位置（原始数组第二大的数）。
第n-1趟排序：
通过这种两两比较，经过n-1趟冒泡就可以将整个数组变为有序数组。并且从示意图中可以看出，红色的22本来就在黑色的22的前面，排序后红色22依然在黑色22前面，这说明冒泡排序不会改变相同数据原来的顺序，这说明，冒泡排序算法是稳定的。
2. 冒泡算法的改进
有时候会有这样的情况，一组数据只有少数数据的顺序不对，而其他数据的顺序都是符合我们需要的顺序的（比如从小到大），比如下图中的情况
这组数据只有前两个位置不符合从小到大的顺序，而后面三个数据都已经符合从小到大的顺序了。此时，只需要一趟排序就可以完成整个数组的排序
但是，如果按照冒泡排序算法的全部流程，需要走完n-1趟排序才能完成，而第一趟冒泡排序之后的剩余流程其实是没有必要的。
这时，可以在冒泡排序中增加一个标志Flag，如果某一趟冒泡排序过程中，没有发生任何数据交换，则认为整个数组已经有序了，不需要在进行下一趟的冒泡排序，算法结束。比如上图中，在第一趟排序后整个数组已经从小到大排序完毕了，第二趟冒泡排序时，没有发生任何数据交换，则不再进行后续的冒泡，算法结束。这样就节省了很多不必要的时间，只需两趟冒泡就可以结束排序，而正常冒泡排序需要四趟冒泡。
3. 改进版冒泡排序代码实现
代码语言：javascript复制//交换 i j 位置的元素
void swap(int array[], int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
//冒泡排序
void bubble_sort(int array[], int num) //数组做函数参数会退化为指针，所以要传入数组元素个数
{
int i = 0, j = 0, ChangeFlag = 1;
for (i = 0; (i < num - 1) && (ChangeFlag == 1); i ) //总共多少趟排序 num - 1
{
ChangeFlag = 0; //默认假设无数据交换
for (j = num - 1; j > i; j--)
{
if (array[j] < array[j - 1])
{
swap(array, j, j - 1);
ChangeFlag = 1;
}
}
}
}冒泡排序的时候，从后往前冒或者从前往后冒都是可以的，也就是代码中的j从num-1开始或者从1开始都可以。
4. 冒泡排序时间复杂度分析
二、选择排序算法
1. 选择排序算法步骤分析
简单选择排序，Simple Selection Sort，用一句简述选择法排序即，每次选择一个最小的元素放在最前面。选择排序的基本思想是，在每一趟排序中，从n-i 1个元素中选择一个最小的元素与i位置上的元素交换，也就是说每次从无序子序列中选择一个最小的元素，并把该元素放在无序子序列的第一个位置上。这样，每趟选择排序需要比较n-i次，只需要交换1次。
第一趟选择排序：
将第1个元素与后面n-1个元素都进行比较 ，选择出一个最小的元素，并把该元素与0位置的元素进行交换，总共需要n-1次比较，1次交换。
经过一趟选择排序后，整个数组的最小元素被放在了0号位置，无序数组的长度只剩下n-1个元素。
第二趟选择排序：
从第二个元素开始的子序列，即（1， 2， 3， 4）的元素，将该无序子序列的第一个元素与后面的每一个元素比较，选择出最小的元素，并和该无序子序列的第一个位置元素进行交换。第二趟选择排序总共进行了n-2次比较，未发生交换（最好的情况是不交换，最差的情况是交换一次）。
经过第二趟选择排序，整个数组最小的两个元素已经按照顺序排在了最前面，有序子序列长度为2，无序子序列长度为n-2。
第n-1趟排序：
第n-1趟排序，要进行n-(n-1)次比较，最多进行一次交换。
2. 选择排序的稳定性分析
假如说有一个序列{5， 6，7， 5， 2， 8 }，第一趟选择排序的时候会把开头的5拿出来和2交换，这样原本在前面的5跑到了另一个5的后面，所以，简单选择排序是不稳定的。
可以看到，原本红色的5在黑色的5前面，经过一趟排序后，红色的5跑去了黑色5的后面。所以，选择排序是不稳定的。
3. 选择排序的代码实现
代码语言：javascript复制/*交换 i j 位置的元素*/
void swap(int array[], int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
/*选择排序*/
void select_sort(int array[], int num)
{
int i = 0, j = 0, MinRecord = 0; /*MinRecord用于记录最小元素的位置*/
for (i = 0; i < num - 1; i )
{
MinRecord = i;
for (j = i 1; j < num; j )
{
if (array[j] < array[MinRecord])
{
MinRecord = j; /*更新最小元素下标*/
}
}
swap(array, i, MinRecord);
}
}4. 选择排序的时间复杂度
三、插入排序算法
1. 插入排序算法步骤分析
直接插入排序，Straight Insertion Sort，是一种最简单的排序方法，它的基本思想就是把一个记录插入到一个有序的序列中，其基本步骤可以概括为两步：一是取出一个元素，留出空位；二是符合条件的元素右移，把取出的元素插入。那么这样的话，我们就需要一个辅助的变量来临时缓存这个被取出的变量，一般我们把这个辅助变量称之为“哨兵”。
第一趟插入排序：
因为是取出一个元素和前一个元素对比，根据大小关系决定插入到第一个元素的左边或者右边，所以第一趟排序应该从第二个元素开始，即i初始值为2。
假设给定一个序列{22， 11， 33， 10， 22}，首先取出第二个元素11，用11和22比较，22大于11则22右移一位，然后把11插入到22的位置，即0号下标处。
在第一趟排序中，进行了一次比较，一次元素移动。通过第一趟排序形成了一个包含两元素的有序子序列。
第二趟插入排序：
取出第三个元素，第三个元素array[2]与第二个元素array[1]对比，若array[2]>array[1]，那么就把array[2]插入到原处，即不进行任何操作，结束本趟插入排序；如果array[2]<array[1]，那么array[1]右移一位，array[2]继续和array[0]比较；如果array[2]>array[0]，那么array[2]插入到1号位置，结束本趟插入排序；如果array[2]<array[0]，那么array[0]右移一位，array[2]插入到0号位置。
第二趟排序进行了一次比较，0次元素移动（这是最好的情况，即本来子序列就已经从小到大了）。经过第二趟排序，有序子序列加一，这也是插入法之所以称为插入的原因：把一个记录插入到一个有序的序列中。
第三趟插入排序：
取出第四个元素，执行比较-移动-插入三部曲操作。
第三趟排序，进行了三次比较，三次移动，这是最坏的情况，即每次比较都要移动。经过第三趟排序，有序序列再次加1，无序序列减一。
第n-1趟插入排序：
第n-1趟插入排序，将进行最少1次比较，0次移动；最多n-1次比较，n-1次移动。
且通过示意图可以看到，红色22本来就在黑色22前面，经过插入排序后，红色22依然在黑色22前面，所以插入排序是稳定排序。
2. 插入排序的代码实现
代码语言：javascript复制/*交换 i j 位置的元素*/
void swap(int array[], int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
/*插入排序*/
void insert_sort(int array[], int num)
{
int i = 0, j = 0, Sentry = 0; /*Sentry 哨兵*/
for (i = 1; i < num; i )
{
Sentry = array[i]; /*取出一个元素*/
j = i - 1;
while ((j >= 0) && (Sentry < array[j]))
{
array[j 1] = array[j]; /*符合条件右移*/
j--;
}
array[j 1] = Sentry;
}
}3. 插入排序的时间复杂度
四、希尔排序
希尔排序又叫缩小增量排序，它是对直接插入排序算法的一种改进。希尔排序算法的基本思想是先将整个待排序的序列划分为若干个子序列，然后分别对子序列排序，逐步缩小划分子序列的间隔，直到划分间隔为1时排序完成。
算法图解
首先给定一个序列[7, 26, 9, 11, 23, 14]
第一趟排序： 按间隔为3划分为三个子序列，对三个子序列分别进行排序，满足从小到大则不动，否则交换两个元素位置。
第二趟排序： 按间隔为2划分子序列，共划分出两个子序列，对两个子序列分别排序
第三趟排序： 按间隔为1划分进行排序
在希尔排序中有一个关键问题就是如何选取划分间隔，一种常用的间隔划分方法是：首先间隔取原始序列长度的一半，在后续排序过程中，后一趟排序的间隔为前一趟排序的间隔的一半。实际上，在业界有一个统一的公式来求划分间隔：gap = gap / 3 1。
算法实现（C语言）
代码语言：javascript复制void shell_sort(int array[], int len)
{
int i = 0, j = 0, k = 0, temp = 0, gap = 0;
gap = len;
do
{
gap = gap / 3 1;
for(i = gap; i < len; i = gap)
{
k = i;
temp = array[k];
for(j = i - gap; (j >= 0) && (array[j] > temp); j -= gap)
{
array[j gap] = array[j];
k = j;
}
array[k] = temp;
}
}
while(gap > 1);
}算法分析
稳定性分析
根据上面的图示可以看出，希尔排序是不稳定的，因为希尔排序是划分子序列对子序列分别排序，如果不同子序列中有相等的数，但它们不在同一子序列中，可能会因为子序列内部排序而改变原有的顺序。比如下图所示，原始序列中有两个11，经过一趟希尔排序后，原本在后面的紫色11跑到了前面位置，所以希尔排序是不稳定的。
复杂度分析
希尔排序并不是简单的随意分组，然后各自排序，希尔排序的精髓在于按照某个增量来划分子序列（最后一个增量必须是1），实现跳跃式移动来提高排序效率，而也正是这种跳跃性带来了不稳定性。希尔排序的时间复杂度是O(nlogn)，希尔排序是最早突破排序算法复杂度O(n×n)的算法之一，从此排序算法时间复杂度不可突破O(n×n)的说法也不攻自破，并且分组划分的思想为后来很多更高效的排序算法提供了思路。
五、快速排序
算法思想
快速排序算法是对冒泡排序算法的一种改进算法，在当前所有内部排序算法中，快速排序算法被认为是最好的排序算法之一。
快速排序的基本思想：
通过一趟排序将待排序的序列分割为左右两个子序列，左边的子序列中所有数据都比右边子序列中的数据小，然后对左右两个子序列继续进行排序，直到整个序列有序。具体实现步骤是这样的，首先从序列中任意选择一个元素，把该元素作为枢轴，然后将小于等于枢轴的所有元素都移到枢轴的左侧，把大于枢轴的元素都移到枢轴的右侧。这样，以枢轴为界，划分出两个子序列，左侧子序列所有元素都小于右侧子序列。枢轴元素不属于任一子序列，并且枢轴元素当前所在位置就是该元素在整个排序完成后的最终位置。这样一个划分左右子序列的过程就叫做快速排序的一趟排序，或称为一次划分。递归此划分过程，直到整个序列有序。
算法图解
首先给出一个无序序列[21, 100, 3, 50, 1]，选取一个元素为基准元素，一般选择序列第一个元素21作为枢轴，然后设置两个指针，一个low指针指向左侧第一个位置，一个high指针指向右侧最后一个位置。
首先取出基准元素21，此时low指向的位置留出一个空位。我们规定，指向空的指针不移动。此时应该操作high指针，如果high指针指向的元素大于基准元素21，那么high指针左移；如果high指针指向的元素小于基准元素21，那么将high指针指向的元素放到low指针指向的空位处。显然，当前high指向的1小于21，所以把1放到low指向的位置，此时high指向为空。
high指针指向空，操作low指针，对low指针：如果low指针指向元素小于基准元素21，那么low指针右移；如果low指针指向元素大于基准元素21，那么把low指针指向的元素放到high指向的空位处。
此时，100大于21，元素放到high，在代码中实际上就是交换low和high指向的元素值。
此时，low指向空，操作high，100大于21，high指针左移。
high指针指向50，依然大于21，high指针继续左移。
当high指向3的时候，3小于21，应交换元素。
此时，high指针指向空，操作low指针，low指向3，小于基准元素21，low指针右移。右移后我们发现，low指针和high指针指向同一个位置，此时将基准元素插入。
最后得到的序列，21左侧全部是小于21的元素，21右侧全部是大于21的元素。并且在本例中，划分好左右序列后，整个序列直接有序了。
算法实现（C语言）
代码语言：javascript复制void qSortArray(int array[], int start, int last)
{
int low = start;
int high = last;
if (low < high)
{
while (low < high)
{
while (array[low] <= array[start] && low < last)
{
low ;//满足小于基准的条件，指针右移
}
while (array[high] >= array[start] && high > start)
{
high--;//满足大于基准的条件，指针左移
}
if (low < high)
{
swap(array[low], array[high]);//交换两个不满足条件的元素
}
else
{
break;
}
}
swap(array[start], array[high]);//插入基准元素
qSortArray(array, start, high - 1);
qSortArray(array, high 1, last);
}
}性能分析
稳定性
由于在快速排序中，元素的比较和交换是跳跃进行的，所以快速排序是一种不稳定的排序算法。比如下图所示，在划分时就改变了序列中两个1原本的顺序，本来在后面的1跑到了前面。
复杂度分析快速排序的平均时间复杂度是O(nlogn)，但是在实际排序中，时间复杂度和基准元素（枢轴）的选择有关。如果枢轴选取不好，那么快速排序有可能就会退化为冒泡排序，时间复杂度为O(n*n)。由于快速排序是通过递归实现的，而递归又要依靠栈空间来实现，所以快速排序相对于其它排序更耗费空间资源。通常来说，为了避免快速排序退化为冒泡排序，以及递归栈过深的问题，我们一般依据“三者取中”的法则来选取基准元素，“三者”即序列首元素、序列尾元素、序列中间元素，在三者中取中值作为本趟快速排序的基准元素。
