前言
正文
一, 选择排序
选择排序是排序中最简单的排序算法,它的操作是这样的: 首先找到数组中最小那个的元素，其次，将它和数组的第一个元素交换位置(如果第一个元素就是最小元素那么它就和自己交换)。再次，剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。它在不断地选择剩余元素之中的最小者。
命题A: 对于长度为N的数组,选择排序需要大约(N^2)/2次比较和N次交换
证明: 可以通过身份的排序轨迹来证明这一点。我们用一张N*N的表格来表示排序的轨迹(上图)，其中每个非红色的数字都表示一次比较。表中大约一半的元素表示黄色的–即对角线和其上部分的元素。对角线上的每个元素都对应一次交换。看代码我们可以更精准得到，0到N-1的任意i都会进行一次交换和N-1-i次比较，因此总共有N次交换以及（N-1）+（N-2）+（N-3）+…+2+1 = N(N-1)/2 ~(N^2)/2次比较。
总的来说，选择排序是一种很容易理解和实现的简单排序算法，它有两个很鲜明的特点。
运行时间和输入无关。为了找出最小元素二扫描一个数组并不能为下一遍扫描提供扫描信息。这种性质在某些情况下是缺点，因为使用选择排序的人可能会惊讶地发现，一个已经有序的数组或者是主键全部相等的数组和一个元素随机排列的数组所用的排序时间竟然一样长！我们将会看到，其他算法会更善于利用输入的初始状态。
数据移动是最小的，每次交换都会改变两个数组元素的值，因此选择排序用了N次交换—交换次数和数组的大小是线性关系。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void show(int * array, int len)
{
for (int i = 0; i < len; ++i)
{
printf(" %d , " , array[i]);
}
printf("\n");
}
/**
* 交换数据
*/
void exchange(int * a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
/**
* 选择排序
* @param array
* @param len
*/
void selection(int * array, int len)
{
for (int i = 0; i < len; ++i)
{
//最小元素的下标
int min_index = i;
for (int j = i; j < len; ++j)
{
if (array[min_index] > array[j])
{
min_index = j;
}
}
//交换元素
exchange(&array[i], &array[min_index]);
/*int temp = array[i];
array[i] = array[min_index];
array[min_index] = temp;*/
}
}
int main(int argc, char *argv[])
{
int array[] = { 78, 23, 56, 12, 1, 100, 23, 11, 9, 2};
int len = sizeof(array) / sizeof(int);
show(&array[0], len);
selection(&array[0], len);
show(&array[0], len);
system("pause");
return 0;
}
二,插入排序
通常人们整理牌的方法是一张一张来的，将每一张牌插入到其他已经有序的牌中的适当位置。在计算机的实现中，为了给要插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。这种说法叫做插入排序。
与选择排序一样，当前索引左边的所有元素都是有序的，但它们的最终位置还不确定，为了给更小的元素腾出空间,它们可能会被移动。但是当索引到达数组的右端时，数组排序就完成了。
和选择排序不同的是，插入排序所需的时间取决于输入中元素的初始顺序。例如，对一个很大且其中元素已经有序(或接近有序)的数组进行排序将会比对随机顺序的数组或是逆序数组进行排序要快得多。
命题B: 对于随机排列的长度为N且主键不重复的数组，平均情况下插入排序需要(N^2)/4次比较以及N^2/4次交换。最坏情况下需要(N^2)/2次交换，最好情况下需要N-1次比较和0次交换。
证明：和命题A一样，通过一个N*N的轨迹表可以很容易就得到交换和比较的次数。最坏情况下对角线之下所有的元素都需要移动位置，最好情况下都不需要。对于随机排列的数组，在平均情况下每个元素都可能向后移动半个数组的长度，因此交换总数是对角线之下的元素总数的二分之一。
比较的总次数是交换的次数加上一个额外的项，该项为N减去被插入的元素正好是已知的最小元素的次数。在最坏情况下(逆序数组)，这一项相对总数可以忽略不计；在最好情况下(数组已经有序)，这一项等于N-1.
/************************************************************************/
/* 插入排序 */
/************************************************************************/
void insertion(int* array, int len)
{
for (int i = 0; i < len; ++i)
{
//判断j下标前面数据是否小于j-1的元素
for (int j = i; j > 0 && array[j] < array[j -1]; --j)
{
//交换元素
exchange(&array[j], &array[j-1]);
/*int temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;*/
}
}
}
插入牌型对于实际应用中常见的某些类型的非随机数组很有效。例如，正如刚才所提到的，想想当你用插入排序对一个有序数组进行排序时会发生什么。插入排序能够立即发现每个元素都已经在合适的位置之上，它的运行时间也是线性的(对于这种数组，选择排序的运行时间是平分级别的)。对于所有主键都相同的数组也会出现相同的情况（因此命题B的条件之一就是主键不重复）
插入排序中重点需要理解概念 '倒置' 这个概念影响到了排序的性能
我们要考虑的更一般的情况是部分优先的数组。倒置指的是数组中的两个顺序颠倒的元素。
比如: 100, 23, 11, 9, 2中有10对倒置:100-23,100-11,100-9,100-2,23-11,23-9,23-2,11-9,11-2,9-2。如果数组中倒置的数量小数组大小的某个倍数，那么我们说这个数组是部分有序的。下面是几种典型的部分有序的数组：
1.数组中每个元素距离它的最终位置都不远； 2.一个有序的大数组接一个小数组 3.数组中只有几个元素的位置不正确
插入牌型对这样的数组很有效，而选择排序则不然。事实上，当倒置的数量很少时，插入排序很可能比其他排序算法都要快的多。
命题C: 插入排序需要的交换操作和数组中倒置的数量相同，需要的比较次数大于等于倒置的数量，小于等于倒置的数量加上数组的大小再减去一。
证明: 每次交换都改变了拉杆顺序颠倒的元素的位置，相当于减少了一对倒置，当倒置数组为0时，排序就完成了。每次交换都对应着一次比较，且1到N-1之间的每个i都可能需要一次额外的比较(在a[i]没有达到数组的左端时)。
总的来说，插入牌型对于部分有序的数组十分高效，也很适合小规模数组。这很重要，因为这些联系的数组在实际应用中经常出现，而且他们也是高级排序算法的中间过程。我们会再学习高级排序算法时再次接触到插入排序。
三, 希尔排序
为了展示初级排序算法性质的价值，接下来我们将学习一种基于插入排序的快速的排序算法。对于大规模乱序数组插入排序很慢，因为它只会交换相邻的元素，因此元素只能一点一点地从数组的一端移动到另一端。例如，如果主键最小的元素正好在数组的尽头，要将它挪到正确的位置就需要N-1次移动。希尔排序为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。
希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。换句话是，一个h有序数组就是h个互相独立的游戏数组编织在一起组成在一起组成的一个数组。在进行排序时，如果h很大，我们就能将元素移动到很远的地方，为实现更小的h有序创造方便。用这种方式，对于任意以1结尾的h序列，我们都能够数组排序。这就是希尔排序。
- 算法的实现使用了序列（1/2(3^k -1)）,从N/3开始递减至1.我们把这个序列称为递增序列。
- 算法实时计算了它的递增序列，另一种方式是将递增序列储存在一个数组中。
实现小二排序的一种方法是对于美国h，用插入排序将h个子数组独立地排序。但因为子数组是相互独立的，一个更简单的方法是在h子数组中将每个元素交换到比它大的元素之前去（将比它大的元素向右移动一格）。只需要再插入排序的代码中将移动元素的距离由1改为h即可。这样希尔排序的实现就转化为一个类似于插入排序但使用不同增量的过程。
希尔排序更高效的原因是它权衡了字数组的规模和有序性，排序之此，各个子数组都很短，排序之后子数组都是部分有序的，这两种抢矿都很适合插入排序。子数组部分有的程度取决于递增序列的选择。理解希尔排序的性能至今是一项挑战。实际上，算法是我们唯一无法准确描述其中对于乱序的数组的性能特征的排序方法。
/************************************************************************/
/*希尔排序 */
/************************************************************************/
void shell(int* array, int len)
{
if (len < 1)
{
return;
}
//因子h 1， 4， 13 ， 40 ...
int h = 0;
while (h > len/3)
{
h = 3 *h +1;
}
while (h > 0)
{
for (int i = 0; i < len; ++i)
{
//判断j下标前面数据是否小于j-h的元素
for (int j = i; j > 0 && array[j] < array[j -h]; j-=h)
{
//交换元素
exchange(&array[j], &array[j-h]);
}
}
h/=3;
}
}
这里h是因子组成新的数组就行排序
h, 2h, 3h, 4h... 这个是使用插入排序的
举一个例子:
[78, 23, 56, 12, 1, 100, 23, 11, 9, 2]
h=4 --> [1, 9]
h=1 --> [78, 23, 56, 12, 1, 100, 23, 11, 9, 2]
如何下载递增序列呢？要回答这个问题并不简单。算法的性能不仅取决于h，还取决于h之间的数学性质，比如它们的公因子等。有很多论文研究了各种不同的递增序列，但都无法证明某个序列是”最好的”。
四,归并排序
归并算法的由来是两个有序的数组归并成一个更大的有序数组。很快人们根据这个操作发明了一种简单的递归排序算法:归并排序。
要将一个数组排序，可以先(递归地)将它分成两半分别排序，然后将结果归并起来。你将会看到，归并排序最吸引人的性质是它能保证将任意长度为N的数组排序所需时间和NlogN成正比；它的主要缺点则是它所需的额外空间和N成正比。简单的归并排序
1, 将两个有序数组合并
将两个有序数组合并 在合并排序中非常重要的步骤。 所有递归的操作都是要调用该方法的。
该方法先将数组中所有的元素复制到new_array的数组中 (new_array的大小和array大小是一样的大的所以不会内存溢出的)，然后在归并到array数组中。
这里就有四个非常重要条件判断: 两个临界点判断，两个比较两个数组中值的大小 1. 左半边用尽(取右半边的元素) 2. 右半边用尽(取左半边的元素) 3. 右半边的前面元素小于左半边的当前元素(取右半边的元素) 4. 右半边的当前元素大于等于左半边的当前元素(取左半边的元素)
/************************************************************************/
/* 合并两个有序的数组数据 [start, mid][mid +1, end] ==> [start, end] */
/************************************************************************/
inline static void merge(int *array, int *new_array/*临时变量*/, int start, int mid, int end)
{
printf("merge start = %d, mid = %d, end = %d\n", start, mid, end);
int i = start; int j = mid + 1;
for (int array_index = start; array_index <= end; ++array_index)
{
new_array[array_index] = array[array_index];
}
for (int array_index = start; array_index <=end; ++array_index)
{
if (j > end ) //
{
array[array_index] = new_array[i++];
}
else if (i > mid)
{
array[array_index] = new_array[j++];
}
else if (new_array[i] > new_array[j])
{
array[array_index] = new_array[j++];
}
else
{
array[array_index] = new_array[i++];
}
}
}
2, 归并算法分别两个模式
归并排序两种模式分别是:
- 自顶向下归并排序
- 最低向上归并排序
① 自顶向下归并排序
归并排序基于合并代码
/************************************************************************/
/* 检查是否有序 */
/************************************************************************/
static bool is_sorted(int *array, int len)
{
for (int i = 0; i < len; ++i)
{
for (int j = i+1; j < len; ++j)
{
if (array[i] > array[j])
{
return false;
}
}
}
return true;
}
/************************************************************************/
/* 排序 */
/************************************************************************/
inline static sort(int *array, int *new_array, int start, int end)
{
for (int i = 0; i < start; ++i)
{
printf("\t");
}
printf("sort start = %d, end = %d\n", start, end);
if (start>= end)
{
return;
}
int position = start + (end - start) / 2;//取中间位置的排序
sort(&array[0], &new_array[0], start, position);
sort(&array[0], &new_array[0], position + 1, end);
merge(&array[0], &new_array[0], start, position, end);
}
/************************************************************************/
/* 归并排序 */
/************************************************************************/
inline static void merge1(int *array, int len)
{
int * new_array = (int*)malloc(len * sizeof(int));
if (!new_array)
{
printf("alloc failed !!!\n");
return;
}
sort(&array[0], &new_array[0], 0, len-1);
if (new_array)
{
free(new_array);
new_array = NULL;
}
}
int main(int argc, char *argv[])
{
int array[] = { 78, 23, 56, 12, 1, 100, 23, 11, 9, 2 };
int len = sizeof(array) / sizeof(int);
printf("len = %d\n", len);
show(&array[0], len);
merge1(&array[0], len);
show(&array[0], len);
assert(is_sorted(&array[0], len));
system("pause");
return 0;
}
下面是归并排序效果图
