数据结构八 希尔排序，快速排序，归并排序，基数排序（桶排序）_随机十个数,分别使用选择排序、希尔排序、快速排序、归并排序和基数排序使数据集

希尔排序是插入排序的改进，因为插入排序比方说是2,3，4,5，6，这时你再插入1，就要依次与前面5个元素比较，很是麻烦，希尔排序相当于把数组分成很多组，第一轮每组的大小是数组的长度/2，第二轮在此基础上继续/2，直到/2后每组长度为0，每轮对每组中的元素从右到左到每个元素进行插入排序.

 public static void shellSort(int[] arr)
    {
        int i,gap;
        //gap这里表示总共要进行几次分组
        for(gap=arr.length/2;gap>0;gap=gap/2)
        {
            //，每次分组之后就进行插入排序，这里的插入排序相当于一次要移动gap个单位，而一般的插入排序一次只移动一个单位
            for(i=gap;i<arr.length;++i)
            {
                int value=arr[i];
                int index=i-gap;
                while (index>=0&&value<arr[index])
                {
                    arr[index+gap]=arr[index];
                    index=index-gap;
                }
                //如果index！=i-gap，说明index根本没有移动，也就是说a[index]比左边所有元素都大，就不需要移动了
                if(index!=i-gap)
                {
                    arr[index+gap]=value;
                }
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

快速排序是以一个数为中轴，通常是数组第一个元素，从右到左，把比其小的元素移到左边，从左到右，把比其大的元素移到右边，实现排序，之后这个数会移动到另一个位置，再分别对左右两部分使用快速排序

要注意的是必须要从j–这个循环开始，主要是因为我们是以第一个数为轴，如果从i那个循环开始，最右边的那个元素就会丢失

    public static void quickSort(int a[],int left,int right) {
        if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
        {
            return ;
        }
        int i = left;
        int j = right;
        int value = a[left];
        //外面的循环i<j这个必须要有，因为如果不加这个判断，使得传入的i>=j，虽然不会执行内部的两个循环
        //但却会执行a[i]=a[j]与a[j]=a[i]
        while(i < j)
        {
            //这里的i<j不是多余的，比如剩下两个元素中，5,4，如果不经过i<j判断，j就会变成-1，并且在移动的过程中，j如果跑到了i的左边，再交换，就会把小的给换到右边去了
            //也不合理的！
            while(i<j&&a[j]>=value)

            {
                j--;
            }
            a[i] = a[j];
            //这里也是同理，如果不判断，i有可能超过了数组的上界
            while(i<j&&a[i]<=value)
            {
                i++;
            }
            a[j] = a[i];
        }
        a[i] = value;
        quickSort(a, left, i - 1);
        quickSort(a, i + 1, right);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

归并排序

public static void mergeSort(int[] arr,int left,int right,int[] temp)
    {
        if(left<right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid,temp);
            mergeSort(arr, mid+1, right,temp);
            merge(arr,left,mid,right,temp);
        }
    }
    public static void merge(int[] arr,int left,int mid,int right,int[] temp)
    {
        int i=left;
        int j=mid+1;
        int x=0;
        //对左右两部分进行比较，每次依次把小的元素添加到辅助数组temp当中
        while(i<=mid&&j<=right)
        {
            if(arr[i]<=arr[j])
            {
                temp[x]=arr[i];
                i++;
                x++;
            }
            else
            {
                temp[x]=arr[j];
                j++;
                x++;
            }
        }
        //因为比较完成之后，肯定是有一个部分的元素还没有添加到temp当中，这时依次对两个部分进行检查。将剩余的元素添加到temp当中
        while(i<=mid)
        {
            temp[x]=arr[i];
            x++;
            i++;
        }
        while(j<=right)
        {
            temp[x]=arr[j];
            x++;
            j++;
        }
        //每一部分进行合并后，就要将temp的数组的值赋给原来的数组，以便进行下一步的排序
        x=0;
        for(i=left;i<=right;++i)
        {
            arr[i]=temp[x];
            x++;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

基数排序
基数排序相当于依次对每个数的各位数进行比较，比较次数以最大数的位数为准，比如最大数为500，是3位，那么会先对个位进行比较，放入到一个二维数组中，再对十位进行比较，然后再对百位进行比较

 public static void radixSort(int[] a)
    {
        int max=a[0];
        int length=a.length;
        for(int i=1;i<a.length;++i)
        {
            if(a[i]>max)
            {
                max=a[i];
            }
        }
        //这是一种很巧妙计算最大数的位数的方法，也可以使用Integer计算最大位数
        int maxLength=(max+"").length();
        //最大数有多少位，基数排序就要进行几轮排序
        int[][] backet=new int[10][a.length];
        //因为后面存放元素的时候，需要知道要存放在每个桶中第几个位置，这里用一个数组来存储相应的位置
        int[] eachIndex=new int[a.length];
        for(int n=0;n<maxLength;++n)
        {
          for(int i=0;i<a.length;++i)
          {
              //x这样算，是为了求出每一轮要求出的位数，如515%10/1=5对应个位，515%100/10对应1，对应十位
              //而515%1000/100=5对应百位
              double x=a[i]%Math.pow(10,n+1)/Math.pow(10,n);
              int m=(int)x;
              backet[m][eachIndex[m]++]=a[i];
          }
          int index=0;
          for(int k=0;k<10;++k)
          {
              if(eachIndex[k]!=0)
              {
                  for(int l=0;l<eachIndex[k];++l)
                  {
                      a[index++]=backet[k][l];
                  }
              }
              //这一步容易被忽略，每次对原数组赋完治后，必须把记录位置的数组归0，以便下一轮排序来用
              eachIndex[k]=0;
          }

        }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43