5

数据结构-排序（三）希尔排序

 2 years ago
source link: https://mr00wang.github.io/2021/12/01/Sort3/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

数据结构-排序（三）希尔排序

1、算法思想

算法思想：

先追求表中元素部分有序，再逐渐逼近全局有序，先将待排序表分割成若干形如 L[i,i+d,i+2d,…,i+kd]L[i,i+d,i+2d,…,i+kd] 的“特殊”子表，对各个子表分别进行直接插入排序，缩小增量d，重复上述过程，直到d = 1为止。 第一趟一般d = n / 2，往后 d = d / 2 。每次将增量缩小⼀半

例子：

对数组【12 28 20 50 48 1 5 28】进行排序

第一趟

第二趟

第三趟

2、代码实现

/**
 * 希尔排序
 * @param arr
 * @param n
 */
void ShellSort(int arr[], int n) {
    int d, j;
    for (d = n / 2; d >= 1; d = d / 2) { //步长变化
        for (int i = d + 1; i <= n ; ++i) {
            if (arr[i] < arr[i - d]) { //arr[i]插入有序增量表
                arr[0] = arr[i]; //暂存
                for (j = i - d; j > 0 && arr[0] < arr[j] ; j -= d) {
                    arr[j + d] = arr[j]; //记录后移，查找插入位置
                }
                arr[j + d] = arr[0]; //插入数据
            }//if
        }//for
    }//for
}

3、算法复杂度分析

时间复杂度：和增量序列 d1, d2, d3… 的选择有关，目前无法用数学手段证明确切的时间复杂度，最坏时间复杂度为 O(n2)O(n2)，当n在某个范围内时，可达O(n1.3)O(n1.3)

空间复杂度： O(1)O(1)

稳定性：不稳定


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK