程序猿修仙之路--算法之希尔排序 (3)

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

   

   

修炼完毕 试炼一下吧

            1                                 c#武器版本             static void Main(string[] args)

       {

             List<int> data = new List<int>() ;

           for (int i = 0; i < 11; i++)            {                                data.Add(new Random(Guid.NewGuid().GetHashCode()).Next(1, 100));            }            //打印原始数组值            Console.WriteLine($"原始数据： {string.Join(",", data)}");            int n = data.Count;            int h = 1;            //计算初始化增量，网络提供，据说比较好的递增因子            while (h < n / 3)            {                h = 3 * h + 1;

           }

            Console.WriteLine($"初始化增量：{h}");

           while (h >= 1)            {                for (int i = h; i < n; i++)                {                    for (int j = i; j >=h&&data[j]<data[j-h]; j-=h)                    {                        //异或法 交换两个变量，不用临时变量                        data[j] = data[j] ^ data[j - 1];                        data[j - 1] = data[j] ^ data[j - 1];                        data[j] = data[j] ^ data[j - 1];                    }                }                h = h / 3;            }            //打印排序后的数组            Console.WriteLine($"排序数据： {string.Join(",", data)}");            Console.Read();        }

运行结果：

原始数据： 47,50,32,42,44,79,10,16,51,74,52

初始化增量：4

排序数据： 10,16,32,42,44,47,50,51,52,74,79

2                                

golang武器版本 

package main
import (
       "fmt" "math/rand"
) func main() {
   var data []int
   for i := 0; i < 11; i++ {
       data = append(data, rand.Intn(100))    }    fmt.Println(data)
       var n = len(data)
       var h = 1 for h < n/3 {    h = 3*h + 1 } fmt.Println(h)
       for h >= 1 {
           for i := h; i < n; i++ {
               for j := i; j >= h && data[j] < data[j-h]; j -= h {
                   data[j], data[j-h] = data[j-h], data[j] }    }    h = h / 3 } fmt.Println(data) }

运行结果：

[81 87 47 59 81 18 25 40 56 0 94]

4

[0 18 25 40 47 56 59 81 81 87 94]