about 10 results (0.02 seconds)

排序算法 - 基数排序(Radix Sort)

by LauCyun Aug 13,2014 22:22:20 7,512 views

基数排序 (Radix Sort) 是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。基数排序的发明可以追溯到 1887 年赫尔曼·何乐礼打孔卡片制表机 (Tabulation Machine)上的贡献。

基数排序法会使用到桶 (Bucket),顾名思义,通过将要比较的位(个位、十位、百位…),将要排序的元素分配至 0~9 个桶中,借以达到排序的作用,在某些时候,基数排序法的效率高于其它的比较性排序法。

所以,排序过程如下:

  • 分配:先从个位开始,根据位值(0-9)分别放到0~9号桶中(比如53,个位为3,则放入3号桶中);
  • 收集:再将放置在0~9号桶中的数据按顺序放到数组中;
  • 重复上面的过程,从个位到最高位,直到排好序为止(比如32位无符号整形最大数4294967296,最高位10位)。

 

1 实例分析

基数排序的方式可以采用LSD(Least sgnificant digital)或MSD(Most sgnificant digital),LSD的排序方式由键值的最右边开始,而MSD则相反,由键值的最左边开始。

以LSD为例,假设有10个数的输入数组如下所示:

[73, 22, 93, 43, 55, 14, 28, 65, 39, 81]

首先根据个位数的数值,在走访数值时将它们分配至编号0到9的桶子中:

0 1 2 3 4 5 6 7 8 9
- 81 22 73 14 55 - - 28 39
      93   65        
      43            

接下来将这些桶子中的数值重新串接起来,成为以下的数列:

[81, 22, 73, 93, 43, 14, 55, 65, 28, 39]

接着再进行一次分配,这次是根据十位数来分配:

0 1 2 3 4 5 6 7 8 9
- 14 22 39 43 55 65 73 81 93
    28              

接下来将这些桶子中的数值重新串接起来,成为以下的数列:

[14, 22, 28, 39, 43, 55, 65, 73, 81, 93]

这时候整个数列已经排序完毕;如果排序的对象有三位数以上,则持续进行以上的动作直至最高位数为止。 

LSD的基数排序适用于位数小的数列,如果位数多的话,使用MSD的效率会比较好,MSD的方式恰与LSD相反,是由高位数为基底开始进行分配,其他的演 算方式则都相同。 

 

2 算法实现

C

 #include <stdio.h>
#include <stdlib.h>

#define N 10              // 数组个数
#define BUCKETS_NUM 10    // 桶个数

void Show(const int *arr, const int n);

int GetNumInPos(int num, int pos);

void Show(const int *arr, const int n) {
    int i;
    for (i = 0; i < n; i++)
        printf("%-4d", arr[i]);
    printf("\n");
}


int GetNumInPos(int num, int pos) {
    int temp = 1;
    for (int i = 0; i < pos - 1; i++)
        temp *= 10;

    return (num / temp) % 10;
}


void RadixSort(int *parray, const int n, const int k) {
    /// 分别为0~9的序列空间
    int *buckets[BUCKETS_NUM];
    for (int i = 0; i < 10; i++) {
        buckets[i] = (int *) malloc(sizeof(int) * (n + 1));
        buckets[i][0] = 0;    // index为0处记录这组数据的个数
    }

    for (int pos = 1; pos <= k; pos++) {
        // 分配过程
        for (int i = 0; i < n; i++) {
            int num = GetNumInPos(parray[i], pos);
            int index = ++buckets[num][0];
            buckets[num][index] = parray[i];
        }

        for (int i = 0, j = 0; i < BUCKETS_NUM; i++) {
            for (int k = 1; k <= buckets[i][0]; k++)
                parray[j++] = buckets[i][k];
            buckets[i][0] = 0;    //复位
        }
    }
}


int main() {
    int array[N] = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81};

    printf("before sorting:\n");
    Show(array, N);

    RadixSort(array, N, 2);

    printf("after sorting:\n");
    Show(array, N);

    return 0;
}

Python

 #!/usr/bin/env python
# -*- coding: utf-8 -*-


def radix_sort(lst, k):
    for k in range(d):  # 排序轮数
        buckets = [[] for i in range(10)]  # 因为每一位数字都是0~9,故建立10个桶

        """
        对于数组中的元素,首先按照最低有效数字进行排序,然后由低位向高位进行。
        """
        for i in lst:
            """
            对于3个元素的数组[977,87,960]:
            第一轮排序首先按照个位数字相同的放在一个桶:s[7]=[977],s[7]=[977,87],s[0]=[960],执行后list=[960,977,87]
            第二轮按照十位数:s[6]=[960],s[7]=[977],s[8]=[87],执行后list=[960,977,87]
            第三轮按照百位:s[9]=[960],s[9]=[960,977],s[0]=87,执行后list=[87,960,977],结束。
            """
            index = int(i / (10 ** k) % 10)  # 73/10=7(小数舍去), 73/100=0
            buckets[index].append(i)
        lst = [j for i in buckets for j in i]
    return lst


unsorted_list = [73, 22, 93, 43, 55, 14, 28, 65, 39, 81]
print(radix_sort(unsorted_list, 2))

 

3 复杂度分析

基数排序的时间复杂度是\({\displaystyle O(k\cdot n)}\),其中\({\displaystyle n}\)是排序元素个数,\({\displaystyle k}\)是数字位数。注意这不是说这个时间复杂度一定优于\({\displaystyle O\left(n\cdot \log \left(n\right)\right)}\)\({\displaystyle k}\)的大小取决于数字位的选择(比如比特位数),和待排序数据所属数据类型的全集的大小;\({\displaystyle k}\)决定了进行多少轮处理,而\({\displaystyle n}\)是每轮处理的操作数目。

以排序\({\displaystyle n}\)个不同整数来举例,假定这些整数以\({\displaystyle B}\)为底,这样每位数都有\({\displaystyle B}\)个不同的数字,\({\displaystyle k=\log _{B}N}\)\({\displaystyle N}\)是待排序数据类型全集的势。虽然有\({\displaystyle B}\)个不同的数字,需要\({\displaystyle B}\)个不同的桶,但在每一轮处理中,判断每个待排序数据项只需要一次计算确定对应数位的值,因此在每一轮处理的时候都需要平均\({\displaystyle n}\)次操作来把整数放到合适的桶中去,所以就有:

\({\displaystyle k\approx \log _{B}N}\)

所以,基数排序的平均时间\({\displaystyle T}\)就是:

\({\displaystyle T\approx \log _{B}\left(N\right)\cdot n}\)

其中前一项是一个与输入数据无关的常数,当然该项不一定小于\({\displaystyle \log n}\)

如果考虑和比较排序进行对照,基数排序的形式复杂度虽然不一定更小,但由于不进行比较,因此其基本操作的代价较小,而且在适当选择的\({\displaystyle B}\)之下,\({\displaystyle k}\)一般不大于\({\displaystyle \log n}\),所以基数排序一般要快过基于比较的排序,比如快速排序。

 

4 参考文档

(全文完)

...

Tags Read More..


排序算法 - 桶排序(Bucket Sort)

by LauCyun Aug 11,2014 20:53:57 12,204 views

桶排序和归并排序有那么点点类似,也使用了归并的思想。大致步骤如下:

  • 设置一个定量的数组当作空桶。
  • Divide - 从待排序数组中取出元素,将元素按照一定的规则塞进对应的桶子去。
  • 对每个非空桶进行排序,通常可在塞元素入桶时进行插入排序。
  • Conquer - 从非空桶把元素再放回原来的数组中。

图1演示了桶排序作用于有10个数的输入数组[4, 47, 60, 93, 29, 3, 52, 75, 22, 86](数据分布在[0,100)之间)上的操作过程:

图1 桶排序过程

 

1 算法实现

伪代码

function bucket-sort(array, n) is
  buckets ← new array of n empty lists
  for i = 0 to (length(array)-1) do
    insert array[i] into buckets[msbits(array[i], k)]
  for i = 0 to n - 1 do
    next-sort(buckets[i])
  return the concatenation of buckets[0], ..., buckets[n-1]

C

 #include <stdio.h>
#include <stdlib.h>

#define ElemType int
#define N 10


void Show(const ElemType *arr, const int n);
void BucketSort(ElemType arr[], int n);


void Show(const ElemType *arr, const int n) {
    int i;
    for (i = 0; i < n; i++)
        printf("%-4d", arr[i]);
    printf("\n");
}


void BucketSort(ElemType arr[], int n) {
    /// 找出最大值和最小值
    ElemType maximum = arr[0], minimum = arr[0];
    int i;
    for (i = 1; i < n; ++i) {
        if (maximum < arr[i]) maximum = arr[i];
        if (minimum > arr[i]) minimum = arr[i];
    }

    /// 创建空桶
    ElemType *buckets;
    int buckets_size = maximum - minimum + 1;
    buckets = (ElemType *) malloc(sizeof(ElemType) * buckets_size);
    for (i = 0; i < buckets_size; ++i) {
        buckets[i] = 0;
    }

    /// 把数据放进桶
    for (i = 0; i < n; ++i) {
        buckets[arr[i] - minimum]++;
    }

    /// 从非空桶把元素再放回原来的数组中
    int j;
    for (i = 0, j = 0; i < buckets_size; i++)
        for (; buckets[i] > 0; (buckets[i])--)
            arr[j++] = i + minimum;

}

int main() {
    ElemType array[N] = {4, 47, 60, 93, 29, 3, 52, 75, 22, 86};

    printf("before sorting:\n");
    Show(array, N);

    BucketSort(array, N);

    printf("after sorting:\n");
    Show(array, N);

    return 0;
}  

Python

#!/usr/bin/env python
# -*- coding: utf-8 -*-


def bucketSort(lst):
    """
        桶排序,建立(maximum-minimum)个桶。
    :param lst: 
    :return: 
    """
    maximum = lst[0]
    minimum = lst[0]
    for i in lst:
        if i > maximum:
            maximum = i
        if i < minimum:
            minimum = i

    buckets_size = maximum - minimum + 1
    buckets = [0] * buckets_size
    for j in range(len(lst)):
        buckets[lst[j] - minimum] += 1

    res = []
    for k in range(buckets_size):
        if buckets[k] != 0:
            res += [k + minimum] * buckets[k]
    return res


def insertionSort(alist):
    """
        插入排序
    :param alist: 
    :return: 
    """
    for index in range(1, len(alist)):
        currentvalue = alist[index]
        position = index
        while position > 0 and alist[position - 1] > currentvalue:
            alist[position] = alist[position - 1]
            position = position - 1

        alist[position] = currentvalue
    return alist


def bucketSort1(lst, maximum):
    """
        桶排序,建立N个桶,N为lst的大小。
    :param lst: 
    :param maximum: 最大值,lst的取值在[0,maximum]之间
    :return: 
    """
    n = len(lst)
    buckets = [[] for i in range(n)]
    for i in range(n):
        index = int(n * lst[i] / maximum)
        buckets[index].append(lst[i])
    res = []
    for i in range(n):
        res.extend(insertionSort(buckets[i]))
    return res


unsortedArray = [4, 47, 60, 93, 29, 3, 52, 75, 22, 86]
print(bucketSort(unsortedArray))
print(bucketSort1(unsortedArray, 100))

 

2 算法过程

如果显示不正常,请戳这里

 

3 复杂度分析

桶排序利用函数的映射关系,减少了几乎所有的比较工作。实际上,桶排序的\(f(k)\)值的计算,其作用就相当于快排中划分,已经把大量数据分割成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做先进的比较排序即可。

\(N\)个关键字进行桶排序的时间复杂度分为两个部分:

  • 循环计算每个关键字的桶映射函数,这个时间复杂度是\(O(N)\)
  • 利用先进的比较排序算法对每个桶内的所有数据进行排序,其时间复杂度为\(\sum_{i=1}^{n} O(N_{i}*logN_{i})\) 。其中\(N_{i}\)为第\(i\)个桶的数据量。

很显然,第(2)部分是桶排序性能好坏的决定因素。尽量减少桶内数据的数量是提高效率的唯一办法(因为基于比较排序的最好平均时间复杂度只能达到\(O(N*logN)\)了)。因此,我们需要尽量做到下面两点:

  • 映射函数\(f(k)\)能够将\(N\)个数据平均的分配到\(M\)个桶中,这样每个桶就有\(\frac{N}{M}\)个数据量。
  • 尽量的增大桶的数量。极限情况下每个桶只能得到一个数据,这样就完全避开了桶内数据的“比较”排序操作。 当然,做到这一点很不容易,数据量巨大的情况下,\(f(k)\)函数会使得桶集合的数量巨大,空间浪费严重。这就是一个时间代价和空间代价的权衡问题了。

对于\(N\)个待排数据,\(M\)个桶,平均每个桶\(\frac{N}{M}\)个数据的桶排序平均时间复杂度为:

\(O(N)+O(M*\frac{N}{M}*log\frac{N}{M})=O(N+N*(logN-logM))=O(N+N*logN-N*logM)\)

\(N=M\)时,即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到\(O(N)\)

总结:桶排序的平均时间复杂度为线性的\(O(N+K)\),其中\(K=N*(logN-logM)\)。如果相对于同样的\(N\),桶数量\(M\)越大,其效率越高,最好的时间复杂度达到\(O(N)\)。当然桶排序的空间复杂度为\(O(N+M)\),如果输入数据非常庞大,而桶的数量也非常多,则空间代价无疑是昂贵的。

 

4 稳定性

桶排序是稳定的。

 

5 海量数据中的应用

应用1

一年的全国高考考生人数为500万,分数使用标准分,最低100,最高900,没有小数,要求对这500万元素的数组进行排序。

分析:对500W数据排序,如果基于比较的先进排序,平均比较次数为\(O(5000000*log5000000)≈1.112\)亿。但是我们发现,这些数据都有特殊的条件:\(100=<score<=900\)。那么我们就可以考虑桶排序这样一个“投机取巧”的办法、让其在毫秒级别就完成500万排序。

方法:创建801(900-100)个桶。将每个考生的分数丢进\(f(score)=score-100\)的桶中。这个过程从头到尾遍历一遍数据只需要500W次。然后根据桶号大小依次将桶中数值输出,即可以得到一个有序的序列。而且可以很容易的得到100分有***人,501分有***人。

实际上,桶排序对数据的条件有特殊要求,如果上面的分数不是从100-900,而是从0-2亿,那么分配2亿个桶显然是不可能的。所以桶排序有其局限性,适合元素值集合并不大的情况。

应用2:

在一个文件中有10G个整数,乱序排列,要求找出中位数。内存限制为2G。只写出思路即可(内存限制为2G意思是可以使用2G空间来运行程序,而不考虑本机上其他软件内存占用情况。)

关于中位数:数据排序后,位置在最中间的数值。即将数据分成两部分,一部分大于该数值,一部分小于该数值。中位数的位置:当样本数为奇数时,中位数=\(\frac{n+1}{2}\) ; 当样本数为偶数时,中位数为\(\frac{n}{2}\)\(\frac{n+1}{2}\)的均值(那么10G个数的中位数,就第5G大的数与第5G+1大的数的均值了)。

分析:既然要找中位数,很简单就是排序的想法。那么基于字节的桶排序是一个可行的方法。

思想:将整型的每1byte作为一个关键字,也就是说一个整形可以拆成4个keys,而且最高位的keys越大,整数越大。如果高位keys相同,则比较次高位的keys。整个比较过程类似于字符串的字典序。

第一步:把10G整数每2G读入一次内存,然后一次遍历这536,870,912即\(\frac{(1024 * 1024 * 1024) * 2}{4}\)个数据。每个数据用位运算>>取出最高8位(31-24)。这8bits(0-255)最多表示256个桶,那么可以根据8bit的值来确定丢入第几个桶。最后把每个桶写入一个磁盘文件中,同时在内存中统计每个桶内数据的数量,自然这个数量只需要256个整形空间即可。

代价:

  • 10G数据依次读入内存的IO代价(这个是无法避免的,CPU不能直接在磁盘上运算)。
  • 在内存中遍历536,870,912个数据,这是一个\(O(n)\)的线性时间复杂度。
  • 把256个桶写回到256个磁盘文件空间中,这个代价是额外的,也就是多付出一倍的10G数据转移的时间。

第二步:根据内存中256个桶内的数量NUM[256],计算中位数在第几个桶中。

很显然,2,684,354,560个数中位数是第1,342,177,280个。假设前127个桶的数据量相加,发现少于1,342,177,280,把第128个桶数据量加上,大于1,342,177,280。说明中位数必在磁盘的第128个桶中。而且在这个桶的第1,342,177,280-N(0-127)个数位上。N(0-127)表示前127个桶的数据量之和。然后把第128个文件中的整数读入内存。(若数据大致是均匀分布的,每个文件的大小估计在10G/256=40M左右,当然也不一定,但是超过2G的可能性很小)。

注意,变态的情况下,这个需要读入的第128号文件仍然大于2G,那么整个读入仍然可以按照第一步分批来进行读取。

代价:

  • 循环计算255个桶中的数据量累加,需要\(O(M)\))的代价,其中m<255。
  • 读入一个大概80M左右文件大小的IO代价。

第三步:继续以内存中的某个桶内整数的次高8bit(他们的最高8bit是一样的)进行桶排序(23-16)。过程和第一步相同,也是256个桶。

第四步:一直下去,直到最低字节(7-0bit)的桶排序结束。我相信这个时候完全可以在内存中使用一次快排就可以了。

整个过程的时间复杂度在\(O(n)\)的线性级别上(没有任何循环嵌套)。但主要时间消耗在第一步的第二次内存-磁盘数据交换上,即10G数据分255个文件写回磁盘上。一般而言,如果第二步过后,内存可以容纳下存在中位数的某一个文件的话,直接快排就可以了。

 

6 参考文档

(全文完)

...

Tags Read More..


排序算法 - 计数排序(Counting Sort)

by LauCyun Aug 10,2014 20:22:20 17,751 views

计数排序,顾名思义,就是对待排序数组按元素进行计数。使用前提是需要先知道待排序数组的元素范围,将这些一定范围的元素置于新数组中,新数组的大小为待排序数组中最大元素与最小元素的差值。

通俗地理解,例如有10个年龄不同的人,统计出有8个人的年龄比A小,那A的年龄就排在第9位,用这个方法可以得到其他每个人的位置,也就排好了序。当然,年龄有重复时需要特殊处理(保证稳定性),这就是为什么最后要反向填充目标数组,以及将每个数字的统计减去1的原因。

算法的步骤如下:

  • 定新数组大小——找出待排序的数组中最大和最小的元素
  • 统计次数——统计数组中每个值为\(i\)的元素出现的次数,存入新数组\(c\)的第\(i\)
  • 对统计次数逐个累加——对所有的计数累加(从\(c\)中的第一个元素开始,每一项和前一项相加)
  • 反向填充目标数组——将每个元素\(i\)放在新数组的第\(c(i)\)项,每放一个元素就将\(c(i)\)减去1

图1演示了计数排序作用于有10个数的输入数组(值的范围为0~15)上的操作过程:

图1 计数排序

其中反向填充主要是为了避免重复元素落入新数组的同一索引处。

当输入的元素是n个0到k之间的整数时,它的运行时间是\(Θ(n + k)\)。计数排序不是比较排序,排序的速度快于任何比较排序算法。

由于用来计数的数组\(c\)的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量时间和内存。例如:计数排序是用来排序0到100之间的数字的最好的算法,但是它不适合按字母顺序排序人名。但是,计数排序可以用在基数排序算法中,能够更有效的排序数据范围很大的数组。

 

1 算法实现

C

#include <stdio.h>
#include <stdlib.h>

#define ElemType int
#define random(x) rand()%(x)
#define N 20         // 数组个数
#define MAXNUM 100   // 待排序的数字范围是0-100


void printArray(ElemType *arr, int n);

void countingSort(ElemType A[], int n, int k);


void printArray(ElemType *arr, int n) {
    int i;
    for (i = 0; i < n; i++)
        printf("%-4d", arr[i]);
    printf("\n");
}


/***
 * 计数排序
 * @param array: 待排序数组
 * @param n: 数组长度
 * @param k: 数组的最大值
 */
void countingSort(ElemType array[], int n, int k) {
    ElemType *ptemp, *pout;
    int i;
    ptemp = (ElemType *) malloc(sizeof(ElemType) * k);
    pout = (ElemType *) malloc(sizeof(ElemType) * n);
    // 初始化ptemp,每个元素都为0
    for (i = 0; i < k; i++)
        ptemp[i] = 0;
    // 统计array中每个值为i的元素出现的次数,存入数组ptemp的第i项
    for (i = 0; i < n; i++)
        ptemp[array[i]] += 1;
    // 对所有的计数累加(从ptemp中的第一个元素开始,每一项和前一项相加)
    for (i = 1; i < k; i++)
        ptemp[i] = ptemp[i - 1] + ptemp[i];
    // 将每个元素i放在新数组的第pout(i)项,每放一个元素就将ptemp(i)减去1
    for (i = n - 1; i >= 0; i--) {
        pout[ptemp[array[i]] - 1] = array[i];
        ptemp[array[i]] -= 1;
    }
    //
    for (i = 0; i < n; i++)
        array[i] = pout[i];
    free(ptemp);
    free(pout);
}

int main(int argc, char **argv) {
    ElemType arr[N];
    int i;
    for (i = 0; i < N; i++)
        arr[i] = random(MAXNUM);

    printf("before sorting:\n");
    printArray(arr, N);

    countingSort(arr, N, MAXNUM);

    printf("after sorting:\n");
    printArray(arr, N);
    return 0;
}

Python

 #!/usr/bin/env python
# -*- coding: utf-8 -*-


import random


def counting_sort(alist, n, max):
    """
        计数排序:当输入的元素是 n 个 0 到 k 之间的整数时(k不能太大,即max不能太大)
    @param alist: 待排序数组
    @:param n: 数组长度
    @param max: 数组中的最大值
    """
    result = [None for i in range(n)]  # 最后的结果
    temp = [0 for i in range(max + 1)]

    # 用数组temp统计每个值=d的元素个数
    for l in alist:
        temp[l] += 1

    # temp[i]表示alist中值<=i的元素个数
    for i in range(1, max + 1):
        temp[i] += temp[i - 1]

    # 将每个元素i放在新数组的第result(i)项,每放一个元素就将temp(i)减去1
    for j in range(n - 1, -1, -1):
        result[temp[alist[j]] - 1] = alist[j]
        temp[alist[j]] -= 1

    return result


N = 20
MAX = 100
unsortedArray = [random.randint(0, MAX) for i in range(N)]
print("before sorting:")
print(unsortedArray)
print("after sorting:")
print(counting_sort(unsortedArray, N, MAX))

 

2 算法过程演示

如果显示不正常,请戳这里

 

3 复杂度分析

最坏、最优和平均的时间复杂度都为\({\displaystyle O(n+k)}\),空间复杂度为\({\displaystyle O(n+k)}\)

 

4 稳定性

计数排序是稳定的。

 

5 应用

优化前向星

前向星不需要像邻接表那样用指针指向下一条边,还是挺方便的。但是,由于前向星初始化需要快排一遍,相对邻接表要慢许多。考虑到一般图论题点数都不会很大,所以可以改为采用计数排序的思想对前向星进行排序。

一开始读入时,先算出每个点出去的边有多少条,然后计算出排序后每个点出去的第一条边位置应在哪里,最后把全部边扫一遍放到排序后应在的位置就好了。

这样排序的话初始化的时间复杂度就降到了\(O(m)\),总体时间并不会逊色于邻接表。

优化后缀数组的倍增算法

如果用快速排序,该算法的复杂度为\(O(nlog^2n)\)。改用计数排序后,复杂度降为\(O(nlogn)\)

 

6 参考文档

(全文完)

...

Tags Read More..


排序算法 - 希尔排序(Shell Sort)

by LauCyun Aug 8,2014 21:20:18 5,759 views

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序属于插入类排序,是将整个有序序列分割成若干小的子序列分别进行插入排序。

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

  • 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率
  • 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位

 

1 算法思想

先取一个正整数\(gap_{1}<n\)作为第一个增量,把所有序号相隔d1的数组元素放一组,组内进行直接插入排序;然后,取第二个增量\(gap_{2}<gap_{1}\),重复上述的分组和排序,直至所取的增量\(gap_{i}=1\),即所有记录放在同一组中进行直接插入排序为止。

下面以一组待排序的8个数据[69, 65, 90, 37, 92, 6, 28, 54]演示希尔排序的过程,如图1所示。

图1 希尔排序过程

2 算法实现

C++

#include<iostream>

using namespace std;
const int N = 8;
using ElemType = int;

void ShellSort(ElemType *array, int n);
void Show(ElemType *array);

void ShellSort(ElemType *array, int n) {
    int gap, i, j;
    ElemType temp;
    for (gap = n >> 1; gap > 0; gap >>= 1) {
        cout << "gap = " << gap << endl;
        for (i = gap; i < n; i++) {
            cout << "i = " << i << " => ";
            for (j = i - gap; j >= 0; j -= gap) {
                if (array[j] > array[j + gap]) {
                    temp = array[j];
                    array[j] = array[j + gap];
                    array[j + gap] = temp;
                }
            }
            Show(array);
        }
        cout << endl;
    }
}

void Show(ElemType *array) {
    for (int i = 0; i < N; i++) {
        printf("%-4d", array[i]);
    }
    cout << endl;
}

int main() {
    ElemType array[N] = {69, 65, 90, 37, 92, 6, 28, 54};
    cout << "排序前:" << endl;
    Show(array);
    cout << "排序过程:" << endl;
    ShellSort(array, N);
    cout << "排序结果:" << endl;
    Show(array);
    return 0;
}

Python

 #!/usr/bin/env python
# -*- coding: utf-8 -*-


def shell_sort(list):
    n = len(list)
    # 初始步长
    gap = n >> 1
    while gap > 0:
        for i in range(gap, n):
            # 每个步长进行插入排序
            temp = list[i]
            j = i
            # 插入排序
            while j >= gap and list[j - gap] > temp:
                list[j] = list[j - gap]
                j -= gap
            list[j] = temp
        # 得到新的步长
        gap = gap >> 1
    return list


unsortedArray = [69, 65, 90, 37, 92, 6, 28, 54]
print(shell_sort(unsortedArray))

 

3 算法过程演示

如果显示不正常,请戳这里

 

4 稳定性

由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。

 

5 复杂度分析

5.1 增量序列的选择

Shell排序的执行时间依赖于增量序列。

好的增量序列的共同特征:

  • 最后一个增量必须为1;
  • 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。

有人通过大量的实验,给出了较好的结果:当\(n\)较大时,比较和移动的次数约在\(n^{1.25}\)\(n^{1.6}\)之间。

5.2 Shell排序的时间性能优于直接插入排序

希尔排序的时间性能优于直接插入排序的原因:

  • 当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
  • 当n值较小时,\(n\)\(n^2\)的差别也较小,即直接插入排序的最好时间复杂度\(O(n)\)和最坏时间复杂度\(O(n^2)\)差别不大。
  • 在希尔排序开始时增量较大,分组较多,每组的记录数目少,故各组内直接插入较快,后来增量\(gap_{i}\)逐渐缩小,分组数逐渐减少,而各组的记录数目逐渐增多,但由于已经按\(gap_{i-1}\)作为距离排过序,使文件较接近于有序状态,所以新的一趟排序过程也较快。

因此,希尔排序在效率上较直接插入排序有较大的改进。

空间复杂度:\(O(n)\)

 

6 参考文档

(全文完)

...

Tags Read More..


排序算法 - 冒泡排序(Bubble Sort)

by LauCyun Aug 7,2014 20:10:00 6,930 views

核心:冒泡,持续比较相邻元素,大的挪到后面,因此大的会逐步往后挪,故称之为冒泡。如图1所示。

图1 Bubble Sort

所以,冒泡排序算法的运作如下:

  • 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  • 针对所有的元素重复以上的步骤,除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

 

1 算法实现

伪代码

function bubble_sort (array, length) {
    var i, j;
    for(i from 0 to length-1){
        for(j from 0 to length-1-i){
            if (array[j] > array[j+1])
                swap(array[j], array[j+1])
        }
    }
}

C++

#include<iostream>

using namespace std;
const int N = 8;
using ElemType = int;

void BubbleSort(ElemType *array);
void Show(ElemType *array);

void BubbleSort(ElemType *array) {
    for (int i = 0; i < N - 1; i++) {
        for (int j = 0; j < N - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                ElemType temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
        // cout << "i = " << i << " => ";
        // Show(array);
    }
}

void Show(ElemType *array) {
    for (int i = 0; i < N; i++) {
        printf("%-4d", array[i]);
    }
    printf("\n");
}

int main() {
    ElemType array[N] = {6, 5, 3, 1, 8, 7, 2, 4};
    Show(array);
    BubbleSort(array);
    Show(array);
    return 0;
}

Python

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def bubbleSort(alist):
    list_len = alist.__len__()
    for i in range(0, list_len):
        print('| i = %s =>' % i, alist)
        for j in range(1, list_len - i):
            if alist[j - 1] > alist[j]:
                alist[j - 1], alist[j] = alist[j], alist[j - 1]
    return alist


unsorted_list = [6, 5, 3, 1, 8, 7, 2, 4]
print(bubbleSort(unsorted_list))

 

2 算法过程演示

如果显示效果不佳,请戳 这里

 

3 复杂度分析

平均情况与最坏情况均为 \(O(n^2)\),使用了 temp 作为临时交换变量,空间复杂度为\( O(1)\)

 

4 参考文档

(全文完)

...

Tags Read More..