一.算法描述
* 先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，具體算法描述：
* 選擇一個(gè)增量序列t1，t2，…，tk，其中ti>tj，tk=1；
* 按增量序列個(gè)數(shù)k，對(duì)序列進(jìn)行k 趟排序；
* 每趟排序，根據(jù)對(duì)應(yīng)的增量ti，將待排序列分割成若干長(zhǎng)度為m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。
* 僅增量因子為1 時(shí)，整個(gè)序列作為一個(gè)表來處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。
二.代碼實(shí)現(xiàn)
private static void shellSort(int[] nums) {
? ? ? ? int mid = (int) Math.floor(nums.length / 2);
? ? ? ? for (; mid > 0; mid = (int) Math.floor(mid / 2)) {
? ? ? ? ? ? for (int i = mid; i < nums.length; i++) {
? ? ? ? ? ? ? ? int j = i;
? ? ? ? ? ? ? ? int current = nums[i];
? ? ? ? ? ? ? ? while (j - mid >= 0 && current < nums[j - mid]) {
? ? ? ? ? ? ? ? ? ? nums[j] = nums[j - mid];
? ? ? ? ? ? ? ? ? ? j = j - mid;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? nums[j] = current;
? ? ? ? ? ? }
? ? ? ? }
? ? }
三.復(fù)雜度分析
時(shí)間復(fù)雜度：平均：O(n1.3)? 最壞：O(n2)? 最好：O(n)
空間復(fù)雜度：O(1)
穩(wěn)定性：不穩(wěn)定
