排序的意义
我们生活中用到的排序的地方非常的多，比如说我们在网上购物的时候就经常可以看到排序的例子，比如说按照价格的升序排序，，按照销量的高低来进行排序等等，这些都是排序的例子，那么他是如何将这些杂乱无章的数据一瞬间变得井然有序的呢？那么他这里就用到了我们这里排序的内容。
冒泡排序
首先来看第一个就是冒泡排序，这个排序大家应该非常的熟悉了，这个排序就是两个循环的嵌套，内部每执行一次循环所干的事情就是将最大的数或者最小的数放到最右边，那我们这里来结合一下图片来看看这个过程，首先我们的数据就是这样：
我们内部的循环就是先将这里最左边的6与他右边相邻的数据进行比较，那么这里相邻的数据就是5，因为我们这里要排的升序的数组，我们这里的6比5要大，所以我们这里就将两个位置的数据进行交换就成了这样：
然后再将这里的6与他右边相邻的数据7进行比较，因为7大于6所以我们这里就不进行交换，但是在下一次的比较就不在是6而是这里的7与他右边相邻的数据进行比较：
那么同样的道理一直循环到最后就成了这样的情况：
那么我们这一个内部的循环得到的结果就是将我们这个数组中的最大值放到了数组的最右边，那再来一次内部的循环呢？是不是就是将我们这里的第二大的数据放到了数组中从右到左的第二个位置上去了，那么我们这里的图就变成了这样：
那么我们这里有个问题我们第二次内部的循环中还需要将数组中从右向左的第二个数据与第一个数据进行比较吗？答案是不需要的这里的原因非常的简单我们就不多解释了，那么我们这里还有一个问题就是我们这里需要进行多少次内部的循环呢？有些小伙伴说啊这里有10个数据，那我们肯定得进行10次内部的循环嘛！那么如果是这么想的小伙伴们那就没有领悟到我们这个排序的意义哈，我们这里有10个数据，我们每进行一次内部的排序都会将最大的数据放到最后面，那么当我们这里排序了九次之后我们是不是就将最大的九个数据放到了最后面啊，那这时就剩下了最后一个数据，那他是不是就一定是最小的数据，所以直接放到最左边不需要任何的操作，那么看了这么多想必大家应该能够理解这个冒泡排序的具体过程，那我们的代码如何来实现呢？大家通过上面的讲述可以很清楚的知道我们这里得通过两个循环的嵌套来实现这个功能，那么既然是嵌套的话我们首先来实现嵌套里面的代码，因为这样符合我们的思维逻辑，那么我们这里就首先创建一个for循环，在for循环里面加一个if语句用来判断与他右边相邻地那个数据谁大谁小，如果右边地数据较小地话我们就执行if语句里面地swap函数来实现调换数据地内容，那么我们这里地代码就如下：
void swap(int* a,int* b)
{
int tem = *a;
*a = *b;
*b = tem;
}
void bubblesort(int* a, int n)
{
assert(a);
for (int i = 0; i < n-1; i++)
{
if (a[i] >a[i + 1])
{
swap(&a[i], &a[i + 1]);
}
}
}
那么我们这里内部循环地代码就写出来了，那写地对不对呢？我们就得来一个测试代码来看看我们这里地正确性：
int main()
{
int a[10] = { 9,8,7,6,5,4,3,2,1 };
bubblesort(a, sizeof(a) / sizeof(a[0]));
for (int i = 0; i < sizeof(a) / sizeof(a[0]);i++)
{
printf("%d ", a[i]);
}
return 0;
}
那么我们执行地结果就如下：
看到这个结果我们这个内部地代码就是真确的了，那么我们就再来写一下外层的代码，那么我们这个外层的循环就是来控制我们这里内部循环的次数的，而且我们知道我们外层循环的次数就是我们数组的元素的个数减一，那么我们这里就直接加一个外层的循环：
void bubblesort(int* a, int n)
{
assert(a);
for (int j = 0; j < n - 1; j++)
{
for (int i = 0; i < n - 1; i++)
{
if (a[i] > a[i + 1])
{
swap(&a[i], &a[i + 1]);
}
}
}
}
那么我们测试一下来看看我们这个代码的正确性：
大家可以看到外面这里测试的代码确实是真确的，但是大家观察我们这里的代码就可以看到外面这里就是简单的两个循环，并没有做出一些简化，外面在文章的上面说了我们的冒泡函数在排序的过程中是会确定一些值的位置的，我们确定了这些位置之后是不用在对其进行比较的，但是我们上面的代码却似乎没有体现出来这一点，所以我们这里就得对其做出修改，我们经过第一次循环我们这里的数组下标为9的位置的元素就已经确定了无需再比较，然后我们再进行一次内部的循环我们下标为8的元素就确定了所以在下一次的循环当中我们就无需再对下标为8或者9的元素做出比较，那么这里我们以此类推就可以发现我们第一要比较的元素是10个而第二次要比较的元素就是9个第三次要比较的元素个数就是8个等等，那么这样的话我们这里直接在第二个for循环中的第二个条件中直接减去一个第一个循环中的j的值不就可以了吗？那么我们这里的代码就如下：
void bubblesort(int* a, int n)
{
assert(a);
for (int j = 0; j < n - 1; j++)
{
for (int i = 0; i < n - 1-j; i++)
{
if (a[i] > a[i + 1])
{
swap(&a[i], &a[i + 1]);
}
}
}
}
而且我们的代码的运行结果也是正确的，看到这里我们的冒泡函数就基本上已经结束了但是这里我们还有个地方得对我们的冒泡函数进行一下改进就是我们这里是对数组中的每个元素都进行比较，但是如果我们给的数组是有序的呢？或者说非常的有序呢？那我们这么写的话是不是还是会一个接着一个的进行比较并且调位，但是这里很有可能我们经过第一次调位的时候我们就已经有序了，但是按照我们上面的代码他还是会进行一系列的比较最后一个元素都没有调，那么这里就是我们代码的不足之处，所以我们这里就得做出一些改进我们在内部循环的外面的创建一个变量并且每次遍历都将这些变量初始化为0，并且每次进入内部循环的if语句的时候我们就将这个变量的值改为1，然后出了内部循环我们就来判断一下这个值是否还等于0，如果等于0的话我们就可以直接执行break语句来结束我们这里的外部循环，那么这样的话我们的代码就会快很多，因为当我们进行了一次内部循环却没有执行一次我们的内部的if语句的话就说明我们此时的数组已经有序了无需再做出调整了，所以就有了我们上面的操作，那么我们改进之后的代码就如下：
void bubblesort(int* a, int n)
{
assert(a);
for (int j = 0; j < n - 1; j++)
{
int flag = 0;
for (int i = 0; i < n - 1-j; i++)
{
if (a[i] > a[i + 1])
{
swap(&a[i], &a[i + 1]);
flag = 1;
}
}
if (flag == 0)
{
break;
}
}
}
那么这里就我们的完整形式。
选择排序
与我们选择排序相似的还有我们这里的选择排序，我们上面的冒泡排序他是每一次内部的循环都是找到数组中的最大或者最小的值，然后将这个值放到最后面，那我们这里的选择排序也是跟他十分的类似，他是每次内部的循环都找到这个数组中的最大值和最小值，找到之后将这个最大值与放到最左边将这个最小值放到最右边，当然我们这里排的是降序，如果是升序的话我们这里就是将最大值放到最右边，将最小值放到最左边，同样的道理我们这里经过一次内部的循环我们将这个数组最左边的值和最右边的值都确定了，那么我们下次再比较和移动的时候就不用管这些位置的数据，那么我们这里就来写写内部的循环的代码：
void selectsort(int* a, int n)
{
int begin = 0;
int end = n - 1;//我们这里的begin和end都是数组中的下标
int max = begin;
int min = begin;//先假设最大值和最小值都是第一个数据
for (int i = begin; i <= end; i++)
{
if (a[i] > a[max])
{
max = i;
}
if (a[i] < a[min])
{
min = i;
}
}
swap(&a[begin], &a[max]);
swap(&a[end], &a[min]);//找到最大最小的数据之后我们就开始交换这里的值
}
那么我们这里就来测试一下我们这个函数正确性：
int main()
{
int a[10] = { 0,1,2,3,4,5,6,7,8,9 };
selectsort(a, sizeof(a) / sizeof(a[0]));
for (int i = 0; i < sizeof(a) / sizeof(a[0]);i++)
{
printf("%d ", a[i]);
}
return 0;
}
我们这里是将数组初始化为：0，1，2，3，4，5，6，7，8，9，那么经过我们上面的操作我们的数组应该就变成了9，1，2，3，4，5，6，7，8，0，那么我们这里就来运行一下这段代码：
哎这里就奇怪了为什么这里会没有发生变化呢？那么我们这里就来进行一下调试首先我们这里的循环是没有问题的经过我们这个循环我们的max的值9，min的值是0
然后我们再来执行我们这里的第一个swap函数，将这里的最大值与开头数据进行交换，那么交换的结果如下：
我们发现此时我们的数组中的数据确实发生了交换，但是这里大家有没有注意到一件事情没我们这里交换的位置是０和９，我们将0放到数组的末尾下标为9，将9放到数组的开头下标为0，但是此时我们的min的值是多少呢？是0！他原本指向的数据是开头的0，但是经过我们上面的处理我们将0移走了，可是我们的min却还是指向原来0的位置，而这个位置已经被其他的数据给占领了，所以我们这里再进行交换的话就会出现了问题，那么我们这里如何来解决呢？大家想一下我们这里出问题的原因是什么？我们这里的情况是算出来min的位置指向了begin，但是经过上面的操作我们将原来begin位置的值放到了max位置上去了，所以为了解决上面的问题我们就得将min的值变成max，那么我们的代码就如下：
void selectsort(int* a, int n)
{
int begin = 0;
int end = n - 1;//我们这里的begin和end都是数组中的下标
int max = begin;
int min = begin;//先假设最大值和最小值都是第一个数据
for (int i = begin; i <= end; i++)
{
if (a[i] > a[max])
{
max = i;
}
if (a[i] < a[min])
{
min = i;
}
swap(&a[begin], &a[max]);
if (min == begin)
{
begin = max;
}
swap(&a[end], &a[min]);//找到最大最小的数据之后我们就开始交换这里的值
}
我们代码的运行结果就如下：
这样的话我们就解决了这个问题，那么我们这里是内部循环的代码，我们这里还得加上一个外部的循环，那么这个外部循环结束的标记是什么呢？是不是当我们begin的值等于或者小于end的时候就结束循环了啊，那么我们这里就采用一个while循环来执行这个完成这个功能，并且还有一点的就是当我们每进行完一次内部循环之后我们都得将这里的end的值减一，将这里begin的值加一，因为我们比较的时候就是根据这个来对我们的i进行赋值，来修改我们这里for循环结束的条件，那么我们这里的代码如下：
void selectsort(int* a, int n)
{
int begin = 0;
int end = n - 1;//我们这里的begin和end都是数组中的下标
while (begin < end)
{
int max = begin;
int min = begin;//先假设最大值和最小值都是第一个数据
for (int i = begin; i <= end; i++)
{
if (a[i] > a[max])
{
max = i;
}
if (a[i] < a[min])
{
min = i;
}
swap(&a[begin], &a[max]);
if (min == begin)
{
begin = max;
}
swap(&a[end], &a[min]);//找到最大最小的数据之后我们就开始交换这里的值
}
end--;
begin++;
}
}
那么我们来看看之前那个代码现在运行的结果：
那么这里就是我们的选择排序的全部过程。
插入排序
我们上面的两个排序都有那么点的相似都是通过对整个数组进行一次整体的遍历然后找到整个数组中的最大值或者最小值，然后将他放到数组的最左边或者最右边，那么从这里开始我们的排序就开始做出一些改变，我们这里的插入排序就好比我们小时候玩的扑克牌，我们在摸牌的时候是不是得对我们的牌进行一些列的排序啊，那么这里的排序是怎么排序的呢？比如说我们此时手中的牌是1 2 2 4 5他是有序排列的然后我们又摸到了一张牌这张牌是3，那么我们这里就会对我们手中的牌进行一下比较我们发现3比这里的2要大，比4要小，所以我们就将3放到2与4之间，1 2 2 3 4 5 这样我们插入了一张牌之后我们的数组还是有序的，然后我们继续摸牌摸到了一张0，那么我们这里就继续对手中的牌从进行一个个有序的比较，那么我们发现这个0比我们这里最小的1还要小，所以我们就将这个0放到1的前面，那么我们手中的牌就变成了0 1 2 2 3 4 5 那么上面摸牌的过程就是我们这里插入排序的思想的一种体现我们再来看看这个排序对于数组是怎么来讲的，我们这是一个数组：
那么我们这里如何来体现一个摸牌的过程呢？虽然我们这里看到的是一个数组，但是我们能不能通过一个指针来只看到这个数组中的一部分呢？比如说我们一开始创建一个指针这个指针指向数组中的第二个元素
那么此时我们这个指针左边的元素是不是有序的？是有序的毕竟就一个元素嘛，那么此时这个指针前面的元素就可以看成我们的手牌，然后我们指针指向的元素就是我们要插入的手牌，那么我们这里的58比14大不需要做出改变，所以我们这里直接将指针指向下一个元素
那么这时我们就再进行一次比较我们将这里的23与58进行比较，因为我们这里排的是升序，而且58比23大，所以我们这里比完之后还得继续比较跟左边的元素进行比较也就是这里的14，然后我们发现14比23大就直接结束了比较，然后将14和指针之间的数据都往后挪动一个位置，再将指针指向的元素放到14的后面，再将指针的值指向下一个元素，那么我们这时的图片就是这样：
同样的道理我们再将这个16进行比较我们发现16比14大比23小所以我们这里就将14与16之间的元素都往后挪动一个位置，然后将16放到14的后面，将指针指向下一个元素，那么此时我们的图就张这样：
那么此时我们的指针前面的值都是有序的而指针后面的值都是等着我们进行插入排序的，那么我们等我们指针将整个数组遍历完之后我们的数组是不是就变得有序起来了，那么通过上面的分析我们看到我们这个排序实现的过程其实是两个循环的嵌套，内部的循环负责将指针指向的值与前面的值进行比较，外部的循环就负责调整我们指针的位置将我们整个数组的元素都遍历一遍，那么还是老道理我们先将内部循环实现，因为我们这里就一个内部的循环所以我们这里就是测试一下，我们将end的值初始化为0，然后创建一个变量tem来记录end的下一个位置的值，因为我们这里将数据往后移动的过程中会存在将数据覆盖的情况，所以我们这里创建一个变量tem来记录一下我们要插入的数据，然后我们这里就创建一个while循环这个循环里面就负责找到这个值应该插入的位置，那么我们这里就创建一个if语句用来判断是否找到了确定的位置，当我们end的值比tem的值大或者相等的话我们就让a[end + 1] = a[end]让数据往后挪动，再让end的值减减，这样我们就可以来比较一个更小的值来确定我们的位置，那么等我们的位置找到之后我们就来插入数据，但是这里要注意的一点就是我们的循环结束之后我们的end其实是没有指向它该插入的位置的，该插入的位置其实是end+1，这里大家可以这么想到我们要插入的数据最小的时候是不是就来到了最后一次比较end的值为0，tem的值比a[end]的值还小，那么这时我们是不是还是会进入if语句里面，然后再让end的值减减这时end的值变成了-1，然后跳出循环，那么我们这时就得插入的数据了，我们应该插入的位置是下标为0的位置，可是我们的end的值是-1，所以我们这里插入的位置就是end+1，那么我们内部循环的代码就如下：
void Insertsort(int* a, int n)
{
int end = 0;
int tem = a[end + 1];
while (end>=0)
{
if (tem <= a[end])
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[++end] = tem;
}
我们来测试一下这个代码的正确性：
int main()
{
int a[10] = { 9,8,7,6,5,4,3,2,1,0 };
Insertsort(a, sizeof(a) / sizeof(a[0]));
for (int i = 0; i < sizeof(a) / sizeof(a[0]);i++)
{
printf("%d ", a[i]);
}
return 0;
}
因为我们这里只进行了一次内部的循环，所以我们这里的结果就应该是将9和8的位置进行了互换，那么我们这个代码运行的结果也就如下：
那么我们这里的内部循环的代码实现是正确的，那么我们再来写写外部循环，那么我们这个外部循环就非常的简单了我们直接写一个for循环，然后将内部循环中的end初始化的0改成i就可以了，那么我们这里的代码就如下：
void Insertsort(int* a, int n)
{
for (int i = 0; i < n-1; i++)
{
int end = i;
int tem = a[end + 1];
while (end >= 0)
{
if (tem <= a[end])
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[++end] = tem;
}
}
那么这里大家要注意的一点就是我们这里的for循环里面的i是要小于n-1的，因为我们内部循环比较的代码是a[end+1],如果是小于n的话我们这里会出现越界访问的情况，这里大家要注意一下，那么我们再来看看运行的结果：
那么我们这里的代码运行的结果就是正确的，我们的代码是实现也就是正确的。
希尔排序
大家看了上面的插入排序，大家应该有没有发现一个现象就是我们的插入排序面对有序的数组的时候排列数据会非常的快比如说我们下面的数组：
面对这样的数组我们在用插入排序的话，会非常的快因为这个数组本身就是有序的，比如说我们要插入这里的2，他会先通过while循环来跟这里的1进行比较而2比1大所以只用了一步我们这里结束了这里的插入，我们在插入3这个数据的时候也是同样的现象，我们的3比这里的2大所以这里也是只用了一步我们这里的3就来到了应该所在的位置，那么同样的道理我们这里的数组越有序我们这个插入排序也就排的越快，当我们的数组本来就是有序的话我们这个插入排序的时间复杂度就是o（N），那我们这里来换一个数组，当我们这个数组长成这样还要排成升序的呢？
我来看插入第一个数据的时候我们要调整一次数据，当我们要插入第二个数据的时候我们要调整两次数据，当我们插入第三个数据的时候要三次数据，那么这么看的话我们这里如果数据越没有序的话我们这里要调整的次数就越多，最坏的情况的话我们这里的时间复杂度就是o(n^2),所以我们这里就发现了一个性质就是我们的插入排序面对有序的数组处理的效率非常的高，但是面对哪种无序的数组处理起来就有点费劲，所以我们这里就得来对其进行一些些改进，我们将间隔为3的元素分成一组，然后对每一组执行插入排序：
大家可以看到这里我们这里就进行了一下分组，相同的元素就是一组那么我们这里就是10 7 4 1 就是一组，9 6 3又是一组 8 5 2又是一组，那么我们这里对这每一个小组都进行插入排序会出现什么样的现象呢？我先对红色的一组执行一下插入排序：
我们发现经过这么个排序我们的最大的值来到了最右边最小的值来到最左边，并且4也来到靠左边，7来到了稍微靠右边，然后我们再对蓝色的一组执行一下插入排序，然后我们的结果就成了这样：
我们发现这个操作也起到了跟上面相同的作用，那么我们这里继续对最后一组执行插入排序
那么我们这里来看看经历了上面的三个排序的结果之后我们的数组成了什么样，我们发现我们的数组好像接近了有序，却没有完全有序，但是这里有一点是非常重要的就是我们这里将较大的元素从最左边移动到了最右边，这样的话我们再对整体进行插入排序的话是不是就会轻松很多啊，因为我们上面分析到插入排序在面对有序数组的时候时间复杂度非常的低，而我们上面这么几步就将我们一个完全无序的数组变的有序了起来，那么我们这里就相当于是对我们这个插入排序进行了一下子优化，那么看到这里我们先将上面所述的操作实现一下，我们定义一个变量gap用来表示我们这里循环的多少组，并且根据我们上面的描述知道我们这里定义的gap有多大我们这里就得执行多少次插入排序，那么我们这里就得加入一个for循环来表示我们这里执行多少次插入排序，而且因为我们这里相同组的元素的下标相差为gap不是1了，所以我们得将里面的插入排序中的1改成gap这样的话才能实现做到分组，并且我们里面的for循环的i也不是从1开始了而是从外部的for循环中的j开始，那么我们这里的代码就如下：
void Shellsort(int* a, int n)
{
int gap = 3;
int j = 0;
for(int j=0;j<gap;j++)
{
for (int i = j; i < n - gap; i += gap)
{
int end = i;
int tem = a[end + gap];
while (end >= 0)
{
if (tem <= a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end += gap] = tem;
}
}
}
我们来看看测试的代码：
int main()
{
int a[10] = { 10,9,8,7,6,5,4,3,2,1 };
Shellsort(a, sizeof(a) / sizeof(a[0]));
for (int i = 0; i < sizeof(a) / sizeof(a[0]);i++)
{
printf("%d ", a[i]);
}
return 0;
}
我们运行的结果就如下：
那么简单的比较一下我们就可以看到这里的结果跟我们之前将的一模一样，但是我们这里的优化并没有结束因为这里大家多分几组的话就可以发现一件事情就是：当我们将间隔为gap的数据分成一组进行插入排序的话我们的gap越大的话我们数组中大的数据就可以越快的跳到数组的后面，小的数据就会越快的跳到前面，但是这样的话我们的数组却不会变的十分有序，那么我们这里就来一个十分极端的情况我们将上面的gap改成10，这样我们只用经过一步就可以将10放到最右边将0放到最左边，但是我们数组不是很有序，与之相反的就是当我们这里的gap越小的话我们这里数据跳的也就越慢，可能大的数据跳到后面需要好几步，但是这样的话我们在执行完这些插入排序的话我们的数组也就会变得更加的有序，比如说我们的gap要是等于1的话我们执行完之后数组直接有序了，那么这么看的话，我们是不是希望取到一个中间的数就是不大也不小然后即跳的快也有序啊，那么这该怎么取呢？答案是取不到，那该怎么办呢?哎我们这里就可以这样我们先将gap的值取大，这样我们大的数据就会很快的来到后面最后我们再取小这样我们的数据就会就会变得更加的有序，而且经过前面的gap较大的插入排序我们大的数据都来到了后面我们较小的gap排序起来也会非常的快，那么我们这里就就一开始将gap初始化为数组的元素除以2，然后每经过一次完整的插入我们就将gap的值再除以2，然后一直重复到gap的值等于1位置，因为我们得用这个来进行一下收尾来保证我们这个数组有序，那么这里为了让我们的代码更加的简介我们将上面的三个循环改成两个，就像这样：
void Shellsort(int* a, int n)
{
int gap = 3;
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tem = a[end+gap];
while (end >= 0)
{
if (tem <= a[end])
{
a[end + gap] = a[end];
end-=gap;
}
else
{
break;
}
a[end +gap] = tem;
}
}
那么这个代码如何来理解呢？我们之前写的方式就可以理解成按照小组进行行动，而我们这里的写的代码就可以看成是齐头并进，大家可以自行理解一下，那么既然我们这里要不停的改变我们这里gap的值，并且每改变一次gap我们都得再进行一次分组的插入所以我们这里就在外面再加一个while循环，这个循环结束的条件就是当gap的值小于等于1的时候，那么我们这里完整的代码就如下：
void Shellsort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 2;
//gap = gap / 3 + 1;//这里也可以每次除以3并且这里的加一是保证我们的gap能取到1
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tem = a[end + gap];
while (end >= 0)
{
if (tem <= a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
a[end + gap] = tem;
}
}
}
}
那么我们再来测试一下我们这里的代码正确性
那么看到这里我们的代码实现就是正确那么我们这里改进之后的代码就是我们所谓的希尔排序。