当你看到这条消息表示我的博客已经正式启用了
Hey, as soon as you are able to read this message, my blog has put into use.
Hey, as soon as you are able to read this message, my blog has put into use.
直接插入排序是一种最简单的排序方法,他的操作是将后面的记录插入到已有的有序序列中。
举个栗子,有一串数字 1 4 2 9 3 8 6 7 5, 要从小到大排序
我们先把他们放进一个数组中,将数组的0号单元作为一个监视哨(当然也可以新开一个变量,可是作把0号单元作为监视哨有一个好处就是不用判断是否越界)
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
-1 | 1 | 4 | 2 | 9 | 3 | 8 | 6 | 7 | 5 |
先看1和2,因为1、2号单元 已经有序,所以不用动
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
-1 | 1 | 4 | 2 | 9 | 3 | 8 | 6 | 7 | 5 |
然后再看2,3。因为4>2,所以不可能有序,于是将2放入监视哨中
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
2 | 1 | 4 | 9 | 3 | 8 | 6 | 7 | 5 |
再找到2该插入的位置。插入位置往后的全部往后移一位
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
2 | 1 | 2 | 4 | 9 | 3 | 8 | 6 | 7 | 5 |
以此类推可以得到结果。
放上代码
template<typename T>
void Simple_Insert_Sort(T item[], size_t length) {
for (int i = 2; i <= length; i++) {
if (item[i - 1] > item[i]) {
item[0] = item[i];
item[i] = item[i - 1];
int j;
for (j = i - 2; item[0] < item[j]; j--) {
item[j + 1] = item[j];
}
item[j + 1] = item[0];
}
}
}
我们可以发现,不管是查找还是移动,时间复杂度都是O(n^2)。我们可以寻求一些优化的方案。
在n很小时可以考虑直接插入排序,当n很大时,很明显的搬家的次数过于多会导致整个程序的效率有所降低,那要找到一种方案来减小移动次数。
首先一种显而易见的方案就是将查找用折半查找,这样可以将查找的时间复杂度降到O(nlogn),可是由于还设计到移动,移动的时间复杂度仍然是O(n^2),故优化不大
将折半查找的方式继续进行优化,由于一般来说,搬家会花费更多的时间,特别是被排序的对象比较大的时候,所以该如何减少移动次数?
2路插入排序就是想运用一块辅助储存空间,将被排序的组一分为二,选择插入在大的之后或者小的之前就可以减少一定的移动次数。
既然显而易见的是,移动比查找更加费时间,那为什么不使用链表的形式避免移动呢
首先来看
1 | 4 | 2 | 9 | 3 | 8 | 6 | 7 | 5 |
---|---|---|---|---|---|---|---|---|
2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 |
第一列是 data域,第二列是next域
其他方法与插入排序相同,但是将数据的插入变成指针的移动,减少了不必要的移动时间
void Linklist_Insert_Sort(int R[], int size) {
int *next;
next = new int[size];
for (int i = 0; i < size - 1; i++) {
next[i] = i + 1;
}
next[size - 1] = 0;
int t = next[next[0]];
next[next[0]] = 0;
while (t) {
int h = 0;
int k = next[t];
while (next[h] && (R[t] > R[next[h]])) {
h = next[h];
}
next[t] = next[h];
next[h] = t;
t = k;
}
for (int i = 0; i < size; i++) {
cout << next[i] << " ";
}
cout << endl;
int i = 1;
int j = next[0];
while (i < size - 1) {
if (i == j) {
i++;
j = next[j];
}
if (i < j) {
int P = next[j];
int temp = R[j];
R[j] = R[i];
R[i] = temp;
next[j] = next[i];
next[i] = j;
i++;
j = P;
}
if (i > j) {
while (i > j)
j = next[j];
}
}
}
最终的boss出场了。
希尔排序是插入排序当中最快的算法,其本质是通过使关键字基本有序来实现最小的移动次数。希尔排序将序列分成k个小的子序列,(k叫做希尔数),例如k=5,则子序列为
data[0],data[5] ;
data[1],data[6];
data[2],data[7];
data[3],data[8];
data[4],data[9];
先让每个子序列有序
然后减小k,如k=3,则心的子序列为
data[0],data[3],data[6],data[9];
data[1],data[4],data[7];
data[2],data[5],data[8];
保证每个子序列有序
再取k=1,使得整个序列有序
void Shell_insert(int data[],int dk, int length){
for(int i=dk+1;i<=length; i++){
if(data[i]>data[i+1]){
data[0]=data[i];
for(int j=i-dk;j>0&&(data[0]<data[j]);j-=dk){
data[j+dk]=data[0];
}
}
}
}
void Shell_Sort(int data[],int length, int shell[]){
for(int i=0;i<length; i++){
Shell_insert(data[],shell[i],length);
}
}
希尔排序有着很神奇的时间复杂度,希尔排序的复杂度由希尔数决定,一般来说,希尔排序可以做到的最好时间复杂度是O(n^(3/2))。