Algorithm - Shell Sort（Java）

柔情只为你懂 2022-05-23 10:28 89阅读 0赞

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击[http://www.captainbed.net][http_www.captainbed.net]

package chimomo.learning.java.algorithm.sort;
 
 import java.util.Arrays;
 
 /**
 * @author Chimomo
 *
 * 
 * Introduction:
 *
 * Shell Sort also called "diminishing increment sort",
 * is improvement of straight insertion sort.
 * 
 *
 * 
 * Basic Thought:
 *
 * Separate the whole sequence into several subsequences,
 * and perform straight insertion sort onto subsequences.
 * Till the whole sequence are basically ordered,
 * perform straight insertion sort onto the whole sequence.
 * 
 *
 * 
 * Algorithm:
 * 1. Take a integer d(1) (less than n) as the first increment,
 * put all the records into the same group whose distance is multiple of d(1),
 * thereby split all the sequence into number of d(1) groups,
 * and perform straight insertion sort in each group.
 * 2. Take the second increment d(2) (less than d(1)),
 * repeating the above grouping and sorting procedure.
 * 3. On the analogy of the above, till the increment d(i)=1,
 * i.e. all the records are grouped in one group and straight insertion sort performed.
 * 
 *
 * 
 * Stability:
 *
 * Shell Sort is not stable.
 * 
 */
 public class ShellSort {
 
 /**
 * Shell Sort
 *
 * @param a The array to be sorted
 */
 private static void shellSort(int[] a) {
 int i = 0, j, k = a.length / 2, t, dk;
 int[] delta = new int[a.length / 2];
 
 // Start from k = a.length / 2, repeat k = k / 2 until k == 0,
 // set the gained k sequence as increment sequence store to delta.
 do {
 delta[i++] = k;
 k /= 2;
 } while (k > 0);
 
 i = 0;
 while ((dk = delta[i]) > 0) {
 for (k = dk; k < a.length; k += dk) {
 
 // Insert a[k] into the ordered increment subsequence
 if (a[k] < a[k - dk]) {
 
 // Backup the element to be inserted, vacate one element position.
 t = a[k];
 for (j = k - dk; j >= 0 && t < a[j]; j -= dk) {
 
 // Move elements backward while searching insertion position
 a[j + dk] = a[j];
 }
 
 // Found the insertion position, insert the element.
 a[j + dk] = t;
 
 // Print each round of sorting result
 System.out.println(Arrays.toString(a));
 }
 }
 
 // Get the next increment value
 ++i;
 }
 }
 
 /**
 * Test program
 *
 * @param args The arguments
 */
 public static void main(String[] args) {
 int[] arr = {11, 16, 22, -3, 99, 0, 16, 6, -1, 99};
 
 System.out.println("Before shell sort:");
 System.out.println(Arrays.toString(arr));
 
 System.out.println("In shell sort:");
 ShellSort.shellSort(arr);
 
 System.out.println("After shell sort:");
 System.out.println(Arrays.toString(arr));
 }
 
 }
 
 /* ------ Running Results ------
 Before shell sort:
 [11, 16, 22, -3, 99, 0, 16, 6, -1, 99]
 In shell sort:
 [0, 16, 22, -3, 99, 11, 16, 6, -1, 99]
 [0, 16, 16, -3, 22, 11, 99, 6, -1, 99]
 [-1, 16, 0, -3, 16, 11, 22, 6, 99, 99]
 [-1, 0, 16, -3, 16, 11, 22, 6, 99, 99]
 [-3, -1, 0, 16, 16, 11, 22, 6, 99, 99]
 [-3, -1, 0, 11, 16, 16, 22, 6, 99, 99]
 [-3, -1, 0, 6, 11, 16, 16, 22, 99, 99]
 After shell sort:
 [-3, -1, 0, 6, 11, 16, 16, 22, 99, 99]
 
 */

[http_www.captainbed.net]: http://www.captainbed.net/troubleshooter