),非稳定排序,原地排序。
主要思想是分治,不过他的分治和合并排序的分治不一样,他是按步长来分组的,而不是想合并那样左一半右一半。
开始步长为整个的长度的一半。
分成nLen/2个组,然后每组排序。
接个步长减为原来的一半在分组排序,直到步长为1,排序之后希尔排序就完成了。
这个思路很好,据说是插入排序的升级版,所以在实现每组排序的时候我故意用了插入排序。
我觉得他是一个特别好的排序方法了。
他的缺点就是两个数可能比较多次,因为两个数据会多次分不过他们不会出现数据的交换。
效率也是很高的。
11.快速排序,堆排序,合并排序,希尔排序的比较,他们的时间复杂的都是n*log(n),我认为在使用上快速排序最广泛,他原地排序,虽然不稳定,可是很多情况下排序根本就不在意他是否稳定。
他的比较次数是比较小的,因为他把数据分成了大和小的两部分。
每次都确定了一个数的位置,所以理论上说不会出现两个数比较两次的情况,也是在最后在交换数据,说以数据交换上也很少。
合并排序和堆排序也有这些优点,但是合并排序要申请额外的空间。
堆排序堆已经排好的数据交换上比快速多。
所以目前快速排序用的要广泛的多。
还有他很容易掌握和实现。
12.计数排序:
n的时间复杂度,稳定排序,非原地排序。
他的思想比较新颖,就是先约定数据的范围不是很大,而且数据都是整数(或能定位到整数)的情况,然后直接申请一个空间。
把要排序的数组A的元素值与申请空间B的下标对应,然后B中存放该下标元素值的个数,从而直接定位A中每个元素的位置。
这样效率只为n。
因为比较很特殊,虽然很快,但是用的地方并不多。
13.
基数排序:
n的时间复杂度,稳定排序,非原地排序。
他的思想是数据比较集中在一个范围,例如都是4位数,都是5位数,或数据有多个关键字,我们先从各位开始排,然后排十位,依次排到最高位,因为我们可以用一个n的方法排一位,所以总的方法为d*n的复杂度。
关键字也一样,我们先排第3个关键字,在排第3个关键字,最后排第一个关键字。
只有能保证每个关键字在n的时间复杂度完成,那么整个排序就是一个d*n的时间复杂度。
所以总的速度是很快的。
不过有一点就是要确保关键字能在n的时间复杂度完成。
14.桶排序:
n的时间复杂度,稳定排序,非原地排序。
主要思路和基数排序一样,也是假设都在一个范围例如概率都在0-1,而且分布还挺均匀,那么我们也是和基数排序一样对一个数把他划分在他指定的区域。
然后在连接这些区域就可以了。
书上对每个区域使用链表的存储,我认为在寸小区域的时候也会有时间在里面。
所以只是理论上的n时间复杂度。
这种思路是不错的。
呵呵。
15.计数排序,基数排序,桶排序的比较,我觉得他们都很有思想,不过都是在特定情况下才能发挥最大的效果。
虽然效率很高,但是用的不会很广泛。
他们之间我更喜欢计数排序,来个映射的方式就直接找到了自己的位置,很高明。
和基数排序和同排序只是理论上的n时间复杂度,基数排序要确定一个关键字的排序是n复杂度的,桶排序要确定每个区域的排序是n复杂度的。
16.排序算法的最后感悟:
黑格尔说过:
存在即合理。
所以这些排序的算法都是很好的,他确实给了我们思想上的帮助。
感谢前人把精华留给了我们。
我得到的收获很大,总结一下各自排序的收获:
冒泡:
好实现,速度不慢,使用于轻量级的数据排序。
插入排序:
也使用于小数据的排序,但是我从他的思想中学到怎么插入一个数据。
呵呵,这样就知道在排好的数据里面,不用再排序了,而是直接调用一下插入就可以了。
选择排序:
我学会了怎么去获得最大值,最小值等方法。
只要选择一下,不就可以了。
合并排序:
我学会分而治之的方法,而且在合并两个数组的时候很适用。
堆排序:
可以用它来实现优先队列,而且他的思想应该给我加了很多内力。
快速排序:
本来就用的最多的排序,对我的帮助大的都不知道怎么说好。
希尔排序:
也是分治,让我看到了分治的不同,原来还有这种思想的存在。
计数排序,基数排序,桶排序:
特殊情况特殊处理。
插入排序
插入排序主要思想是:
把要排序的数字插入到已经排好的数据中。
例如12356是已经排好的序,我们将4插入到他们中,时插入之后也是排好序的。
这里显而易见是插入到3的后面。
变为123456.实现思路:
插入排序就是先是一个有序的数据,然后把要插入的数据插到指定的位置,而排序首先给的就是无序的,我们怎么确定先得到一个有序的数据呢?
答案就是:
如果只有一个,当然是有序的咯。
我们先拿一个出来,他是有序的,然后把数据一个一个插入到其中,那么插入之后是有序的,所以直到最后都是有序的。
。
结果就出来了!
当然在写的时候还是有一个技巧的,不需要开额外的数组,下标从第二个元素开始遍历知道最后一个,然后插入到前面已经有序的数据中。
这样就不会浪费空间了。
插入排序用处还是很多的,特别是链表中,因为链表是指针存放的,没有数组那么好准确的用下标表示,插入是简单有效的方法。
源代码
1 #include
2 #include
4 //插入排序从下到大,nData为要排序的数据,nNum为数据的个数,该排序是稳定的排序
5 bool InsertionSort(int nData[], int nNum)
6 {
7 for (int i = 1; i < nNum; ++i) //遍历数组,进行插入排序
8 {
9 int nTemp = nData[i];
10 for (int j = 0; j < i; ++j) //对该数,寻找他要插入的位置
11 {
12 if (nData[j] > nTemp) //找到位置,然后插入该位置,之后的数据后移
13 {
14 for (int k = i; k > j; --k) //数据后移
15 {
16 nData[k] = nData[k -1];
17 }
18 nData[j] = nTemp; //将数据插入到指定位置
19 break;
20 }
21 }
22 }
24 return true;
25 }
27 int main()
28 {
29 int nData[10] = {4,10,9,8,7,6,5,4,3,2}; //创建10个数据,测试
30 InsertionSort(nData, 10); //调用插入排序
32 for (int i = 0; i < 10; ++i)
33 {
34 printf("%d ", nData[i]);
35 }
37 printf("\n");
38 system("puase");
39 return 0;
40 }
冒泡排序
冒泡排序的主要思路:
我们把要排序的数组A={3,4,2,1}看成一组水泡,
--[endif]-->就像冒泡一样,轻的在上面,重的在下面,换成数据,就是小的在上面,大的在下面。
我们先把最轻的冒出到顶端,然后冒出第二轻的在最轻的下面,接着冒出第三轻的。
依次内推。
直到所有都冒出来了为止。
3.我们怎么做到把最轻的放在顶端呢?
我们从最底下的数据开始冒,如果比他上面的数据小,就交换(冒上去),然后再用第二第下的数据比较(此时他已经是较轻的一个),如果他比他上面的小,则交换,把小的冒上去。
直到比到第一位置,得到的就是最轻的数据咯,这个过程就像是冒泡一样,下面的和上面的比较,小的冒上去。
大的沉下来。
画个图先:
最初
第一次结果
第二次结果
第三次结果
3
3
3
1
4
4
1
3
2
1
4
4
1
2
2
2
开始:
1和2比,1比2小,浮上,然后1跟4比,再1跟3比,这样结构就变为1,3,4,2。
最小的位置确定了,然后我们确定第二小的,同理2vs4,2vs3得到2,再确定第3小数据,3vs4得到3,最后就是4为最大的数据,我们冒泡就排好了。
注:
这里红色的1,2是前一次比较1vs2交换的结构。
后面也一样。
大概思路就这样了,奉上源代码:
#include
#include
//冒泡排序, pnData要排序的数据, nLen数据的个数
int BubbleSort(int* pnData, int nLen)
{
bool isOk = false; //设置排序是否结束的哨兵
//i从[0,nLen-1)开始冒泡,确定第i个元素
for (int i = 0; i < nLen - 1 && !
isOk; ++i)
{
isOk = true; //假定排序成功
//从[nLen - 1, i)检查是否比上面一个小,把小的冒泡浮上去
for (int j = nLen- 1; j > i; --j)
{
if (pnData[j] < pnData[j - 1]) //如果下面的比上面小,交换
{
int nTemp = pnData[j];
pnData[j] = pnData[j - 1];
pnData[j - 1] = nTemp;
isOk = false;
}
}
}
return 1;
}
int main()
{
int nData[10] = {4,10,9,8,7,6,5,4,3,2}; //创建10个数据,测试
BubbleSort(nData, 10); //调用冒泡排序
for (int i = 0; i < 10; ++i)
{
printf("%d ", nData[i]);
}
printf("\n");
system("pause");
return 0;
}
选择排序
选择排序和冒泡排序思路上有一点相似,都是先确定最小元素,再确定第二笑元素,最后确定最大元素。
他的主要流程如下:
1.加入一个数组A = {5,3,6,2,4,7},我们对他进行排序
2.确定最小的元素放在A[0]位置,我们怎么确定呢,首先默认最小元素为5,他的索引为0,然后用它跟3比较,比他打,则认为最小元素为3,他的索引为1,然后用3跟6比,发现比他小,最小元素还是3,然后跟2比,最小元素变成了2,索引为3,然后跟4比,跟7比。
当比较结束之后,最小元素也尘埃落定了。
就是2,索引为3,然后我们把他放在A[0]处。
为了使A[0]原有数据部丢失,我们使A[0](要放的位置) 与A[3](最小数据的位置)交换。
这样就不可以了吗?
3.然后我们在来找第二小元素,放在A[1],第三小元素,放在A[2]。
。
当寻找完毕,我们排序也就结束了。
4.不过,在找的时候要注意其实位置,不能在找A[2]的时候,还用A[2]的数据跟已经排好的A[0],A[1]比,一定要跟还没有确定位置的元素比。
还有一个技巧就是我们不能每次都存元素值和索引,我们只存索引就可以了,通过索引就能找到元素了。
5.他和冒泡的相似和区别,冒泡和他最大的区别是他发现比他小就交换,把小的放上面,而选择是选择到最小的在直接放在确定的位置。
选择也是稳定的排序。
基本思路就这样了,奉上源代码:
#include
#include
//选择排序, pnData要排序的数据, nLen数据的个数
int SelectSort(int* pnData, int nLen)
{
//i从[0,nLen-1)开始选择,确定第i个元素
for (int i = 0; i < nLen - 1; ++i)
{
int nIndex = i;
//遍历剩余数据,选择出当前最小的数据
for (int j = i + 1; j < nLen; ++j)
{
if (pnData[j] < pnData[nIndex])
{
nIndex = j;
}
}
//如果当前最小数据索引不是i,也就是说排在i位置的数据在nIndex处
if (nIndex !
= i)
{
//交换数据,确定i位置的数据。
int nTemp = pnData[i];
pnData[i] = pnData[nIndex];
pnData[nIndex] = nTemp;
}
}
return 1;
}
int main()
{
int nData[10] = {4,10,9,8,7,6,5,4,3,2}; //创建10个数据,测试
SelectSort(nData, 10); //调用选择排序
for (int i = 0; i < 10; ++i)
{
printf("%d ", nData[i]);
}
printf("\n");
system("pause");
return 0;
}
希尔排序
希尔排序,他的主要思想借用了合并排序的思想。
不过他不是左边一半右边一半,而是按照步长来分,随着步长减少,分成的组也越少。
然后进行各组的插入排序。
主要思路就是这样。
#include
#include
//对单个组排序
int SortGroup(int* pnData, int nLen, int nBegin,int nStep)
{
for (int i = nBegin + nStep; i < nLen; i += nStep)
{
//寻找i元素的位置,
for (int j = nBegin; j < i; j+= nStep)
{
//如果比他小,则这里就是他的位置了
if (pnData[i] < pnData[j])
{
int nTemp = pnData[i];
for (int k = i; k > j; k -= nStep)
{
pnDat