Articles in the category of 默认分类

默认分类

直接插入排序

直接插入排序是一种最简单的排序方法,他的操作是将后面的记录插入到已有的有序序列中。

举个栗子,有一串数字 1 4 2 9 3 8 6 7 5, 要从小到大排序

我们先把他们放进一个数组中,将数组的0号单元作为一个监视哨(当然也可以新开一个变量,可是作把0号单元作为监视哨有一个好处就是不用判断是否越界)

0123456789
-1142938675

先看1和2,因为1、2号单元 已经有序,所以不用动

0123456789
-1142938675

然后再看2,3。因为4>2,所以不可能有序,于是将2放入监视哨中

0123456789
214 938675

再找到2该插入的位置。插入位置往后的全部往后移一位

0123456789
2124938675

以此类推可以得到结果。

放上代码

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路插入排序

将折半查找的方式继续进行优化,由于一般来说,搬家会花费更多的时间,特别是被排序的对象比较大的时候,所以该如何减少移动次数?

2路插入排序就是想运用一块辅助储存空间,将被排序的组一分为二,选择插入在大的之后或者小的之前就可以减少一定的移动次数。

表插入排序

既然显而易见的是,移动比查找更加费时间,那为什么不使用链表的形式避免移动呢

首先来看

142938675
234567890

第一列是 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))。

- Read More -
This is just a placeholder img.