【十大排序总结】（JAVA）

墨蓝 2022-04-17 02:00 179阅读 0赞

### 文章目录 ###

*   *  排序总结
     *   *  冒泡排序
         *  桶排序
         *  标准的桶排序
         *  插入排序
         *  希尔排序
         *  选择排序
         *  计数排序
         *  基数排序
         *  堆排序
         *  归并排序
         *  快速排序
         *  三路快排

## 排序总结 ##

### 冒泡排序 ###

\*\* 描述\*\*

对一个数组进行排序,冒泡乃经典的排序之一，我们可能遇到数组排序时，首先想到的可能就是冒泡排序了。只是我们只凭着直觉去用着，而不知到其名字。

**实现步骤**

*  一个外层循环控制循环次数，也就是相邻两个元素比较的最大次数，每次把最大移到不超过外层的限制。
 *  一个内层循环，比较相邻元素，次数不超过外层的控制次数，把最大的元素移动到相应的位置。

package DS_Sort_bubble;
    
    import java.util.Arrays;
    
    /** * Created by 张超帅 on 2018/10/16. */
    public class bubble { 
        public static void sort(int[] nums ){ 
            int len = nums.length;
            for(int i = len - 1; i > 0; i --) { 
                for(int j = 0; j < i; j ++) { 
                    if(!less(nums[j], nums[j + 1])) { 
                        exch(nums, j, j+1);
                    }
                }
                System.out.println("第 " + (len - i) + " 次排序： " + Arrays.toString(nums));
            }
        }
        public static Boolean less(int x, int y) { 
            return x < y ? true : false;
        }
        public static void exch(int[] a, int x, int y) { 
            int temp = a[x];
            a[x] = a[y];
            a[y] = temp;
        }
        public static void main(String[] args) { 
            int a[] = { 9,6,3,1,-4,-5,-9};
            System.out.println("排序前的数组： " + Arrays.toString(a));
            sort(a);
            System.out.println("排序后的数组： " + Arrays.toString(a));
    
        }
    }

**结果显示**

排序前的数组： [9, 6, 3, 1, -4, -5, -9]
    第 1  次排序： [6, 3, 1, -4, -5, -9, 9]
    第 2  次排序： [3, 1, -4, -5, -9, 6, 9]
    第 3  次排序： [1, -4, -5, -9, 3, 6, 9]
    第 4  次排序： [-4, -5, -9, 1, 3, 6, 9]
    第 5  次排序： [-5, -9, -4, 1, 3, 6, 9]
    第 6  次排序： [-9, -5, -4, 1, 3, 6, 9]
    排序后的数组： [-9, -5, -4, 1, 3, 6, 9]

**复杂度分析**

*  时间复杂度：O(N^2)~O(N)
 *  空间复杂度：O(N^2)

### 桶排序 ###

**描述**

这个排序是非常占用空间的，大概是这样子的，你有多大数范围，就把最大的数，当作数组的大小，当然也得必须能在数组的承受范围之内。

**步骤**

*  根据数据的范围，选择合适大小的数组容量大小。
 *  遍历数据，数组的`index`代表所输入的数据，数组的值代表此index有多少个。
 *  然从前到后进行输出，条件是数组值非0；

package DS_Sort_bucket;
    
    /** * Created by 张超帅 on 2018/10/28. */
    public class bucket { 
        public static void sort(int[] a){ 
            int[] count = new int[10];
            for(int i = 0; i < a.length; i ++) { 
                count[a[i]]++;
            }
            for(int j = 0; j < 10; j ++) { 
                while (count[j] != 0){ 
                    System.out.print(j + " ");
                    count[j] --;
                }
            }
            System.out.println();
        }
        public static void print(int[] a) { 
            for(int x : a) { 
                System.out.print(x + " ");
            }
            System.out.println();
        }
        public static void main(String[] args) { 
            int[] a = { 1, 3, 4, 5 , 6, 6, 6, 7, 3, 2, 1};
            sort(a);
            //print(a);
        }
    }

**结果**

1 1 2 3 3 4 5 6 6 6 7

**复杂度分析**

*  时间复杂度 ：O(N)
 *  空间复杂度：O(N)

### 标准的桶排序 ###

**描述**

一直以为上面就是桶排序，但今天看来算法导论讲的排序和自己写的完全不一致，思想有点相似。桶排序划分了相同大小的子区间，称为“桶”。然后将数据均匀的分布在相应的区间。

**步骤**

*  计算出需要几个桶。
 *  初始化桶。
 *  将数据存入相应的桶中。
 *  对每个桶的数据进行排序。

**代码**

package DS_Sort_Bucket2;
    
    import java.util.ArrayList;
    import java.util.Collection;
    import java.util.Collections;
    
    /** * Created by 张超帅 on 2018/11/9. */
    
    public class DS_Sort_Bucket2 { 
        public static void sort(int[] nums) { 
            int len = nums.length;
            int max = Integer.MIN_VALUE;
            int min = Integer.MAX_VALUE;
            for(int i = 0; i < len; i ++) { 
                min = Math.min(min, nums[i]);
                max = Math.max(max, nums[i]);
            }
            //Work out bucket's size
            int bucketNum = (max - min)/len + 1;
            ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>();
            System.out.println(bucketNum);
            //initial every bucket
            for(int i = 0; i < bucketNum; i ++) { 
                bucketArr.add(new ArrayList<Integer>());
            }
            //nums of Arrays is gived corresponding bucket
            for(int i = 0; i < len; i ++) { 
                int num = (nums[i] - min) / len;
                bucketArr.get(num).add(nums[i]);
            }
            //The number of sorted within every bucket
            for(int i = 0; i < bucketArr.size(); i ++) { 
                Collections.sort(bucketArr.get(i));
            }
            //print each bucket's number
            System.out.println(bucketArr.toString());
        }
        public static void main(String[] args) { 
            int[] a = { 1,9,1,3,6,8,1,1};
            sort(a);
        }
    }

**复杂度分析**

*  时间复杂度：O（N）
 *  空间复杂度：O（N）

### 插入排序 ###

**描述**

每次，左边的数是已排好的序列，将右边的数插入到已经排好序的数组中的相应的位置。

**步骤**

*  第一个循环的变量`i`表示前边已经排好序的数组。
 *  第二个循环将第`i`个数插入已经排好的数组的正确位置。
 *  打印列表

**代码**

package DS_Sort_insert;
    
    import java.util.Arrays;
    
    /** * Created by 张超帅 on 2018/10/16. */
    public class insert { 
        public static void sort(int[] a) { 
            int len = a.length;
            for(int i = 1; i < len; i ++) { 
                for(int j = i; j >0; j--) { 
                    if(less(a[j], a[j-1])) exch(a, j, j - 1);
                }
                System.out.println("第 " + i + " 次排序: " + Arrays.toString(a) );
            }
        }
        public static Boolean less(int a, int b) { 
            return  a < b ? true : false;
        }
        public static void exch(int[] a, int i, int j) { 
            int temp = a[i]; a[i] = a[j]; a[j] = temp;
        }
    
        public static void main(String[] args) { 
            int a[] = { 2,4,1,0,-3,6,9};
            System.out.println("排序前的数组： " + Arrays.toString(a));
            sort(a);
            System.out.println("排序后的数组： " + Arrays.toString(a));
        }
    }

**结果**

排序前的数组： [2, 4, 1, 0, -3, 6, 9]
    第 1  次排序:  [2, 4, 1, 0, -3, 6, 9]
    第 2  次排序:  [1, 2, 4, 0, -3, 6, 9]
    第 3  次排序:  [0, 1, 2, 4, -3, 6, 9]
    第 4  次排序:  [-3, 0, 1, 2, 4, 6, 9]
    第 5  次排序:  [-3, 0, 1, 2, 4, 6, 9]
    第 6  次排序:  [-3, 0, 1, 2, 4, 6, 9]
    排序后的数组： [-3, 0, 1, 2, 4, 6, 9]

**复杂度分析**

*  时间复杂度： O（N^2）
 *  空间复杂度： O（N^2）

### 希尔排序 ###

**描述**

这个排序是建立在插入排序的基础上，而且对于一些较乱序的数组来说，插入排序需要很多的移动次数。而希尔排序对局部进行排序，可以跨很远交换两个数。

**代码**

package DS_Sort_shell;
    
    import java.util.Arrays;
    
    /** * Created by 张超帅 on 2018/10/16. */
    public class shell { 
    
        public static void sort(int[] a) { 
            int len = a.length;
            int h = 1;
            while(h < len/ 3) h = h*3 + 1;
            while( h >= 1) { 
                for(int i = h; i < len; i ++) { 
                    for(int j = i; j >= h; j -= h) { 
                        if(less(a[j] , a[j - h])){ 
                            exch(a, j, j - h);
                        }
                    }
                }
                h /= 3;
            }
        }
        public static Boolean less(int x, int y) { 
            return x < y ? true : false;
        }
        public static void exch(int[] a, int x, int y) { 
            int temp = a[x];
            a[x] = a[y];
            a[y] = temp;
        }
        public static void main(String[] args) { 
            int a[] = { 9,2,4,1,0,-3,6,9};
            System.out.println("排序后的数组： " + Arrays.toString(a));
            sort(a);
            System.out.println("排序后的数组： " + Arrays.toString(a));
        }
    }

**结果**

排序后的数组： [9, 2, 4, 1, 0, -3, 6, 9]
    排序后的数组： [-3, 0, 1, 2, 4, 6, 9, 9]

### 选择排序 ###

**描述**

每次从剩余数组后边的数中，选择一个最大数，将其放到第i处。

**代码**

package DS_Sort_select;
    
    
    import java.util.Arrays;
    
    /** * Created by 张超帅 on 2018/10/16. */
    public class Select { 
        public static void sort(int[] a) { 
            int len = a.length;
            for(int i = 0; i < len; i ++) { 
                int min_index = i;
                for(int j = i + 1; j < len; j ++) {  //从i+1后边的元素中，每次挑选最小的放到第i处.
                    if(a[j] < a[min_index]) { 
                        min_index = j;
                    }
                }
                exch(a, i , min_index);
                System.out.println("第 " + i + " 次排序： " + Arrays.toString(a));
            }
        }
        public static void exch(int[] a, int i, int j) { 
            int temp = a[i]; a[i] = a[j]; a[j] = temp;
        }
        public static void main(String[] args) { 
            int a[] = { 2,4,1,0,-3,6,9};
            sort(a);
            System.out.println(Arrays.toString(a));
        }
    }

### 计数排序 ###

**描述**

在一定范围内的元素，利用一个数组进行计数，然后按照其记录的相应的位置进行输出。

计数排序是比较稳定的。

**步骤**

*  初始化数组。一个输出的数组，一个计数的数组。
 *  遍历数组，将其存入计数的数组中，下标代表其数值，计数的数组值代表其出现的次数。
 *  将计数的数组进行累加，这样得出的每个值代表小于其索引值的数的个数。
 *  从后往前进行遍历，这样的话，按照计数数组的值将其给与输出的数组的对应的位置。遇到相同的数会往前插入其值。

package DS_Sort_Count;
    
    import java.util.Arrays;
    
    /** * Created by 张超帅 on 2018/10/28. */
    public class count { 
        public static int[] sort(int[] a, int k) { 
            int len = a.length;
            int[] res = new int[len];
            int[] count = new int[k];
            for(int i = 0; i < len; i ++) { 
                count[a[i]] ++;
            }
            for(int i = 1; i < k; i ++) { 
                count[i] += count[i-1];
            }
            for(int i = len - 1; i >= 0; i --) { 
                res[--count[a[i]]] = a[i];
            }
            return res;
        }
        public static void main(String[] args) { 
            int[] a = { 1, 4, 2, 4, 3, 1, 6, 4, 5};
            System.out.println("排序前的数组：" + Arrays.toString(a));
            int[] res = sort(a, 7);
            System.out.println("排序后的数组：" + Arrays.toString(res));
        }
    }

**结果**

排序前的数组：[1, 4, 2, 4, 3, 1, 6, 4, 5]
    排序后的数组：[1, 1, 2, 3, 4, 4, 4, 5, 6]

### 基数排序 ###

**描述**

从直观上看，从个位数开始排序，到最大的位数`d`,每次排序，借助上次的计数排序进行操作，因为每个位数的数字不超过10。

**步骤**

*  一个循环控制从个位到最高位
 *  在这个循环中每次循环进行一次计数排序。
 *  最后得到的数组便是排好序的数组。

**代码**

package DS_Sort_Radix;
    
    import java.util.Arrays;
    
    /** * Created by 张超帅 on 2018/10/27. */
    public class redix { 
    
        public static int[] sort(int [] a, int d) { 
            int len = a.length;
            int[] res = new int[len];
            int[] count = new int[10];
            for(int i = 0, rate = 1; i < d; i ++) { 
                Arrays.fill(count, 0);
                System.arraycopy(a, 0, res, 0, len);
                for(int j = 0; j < len; j ++) { 
                    count[(res[j]/rate) % 10] ++;
                }
                for(int j = 1; j < 10; j ++) { 
                    count[j] += count[j - 1];
                }
                for(int j = len - 1; j >= 0; j --) { 
                    a[--count[(res[j]/rate) % 10]] = res[j];
                }
                rate *= 10;
            }
            return a;
        }
        public static void main(String[] args) { 
            int a[] = { 12, 130, 345,234, 234, 235, 335, 203, 346, 34530,345,6436,2345,1235,4532};
            System.out.println("排序前的数组： " + Arrays.toString(a));
            int[] res = sort(a, 5);
    
            System.out.println("排序后的数组： " + Arrays.toString(res));
        }
    }

排序前的数组： [12, 130, 345, 234, 234, 235, 335, 203, 346, 34530, 345, 6436, 2345, 1235, 4532]
    排序后的数组： [12, 130, 203, 234, 234, 235, 335, 345, 345, 346, 1235, 2345, 4532, 6436, 34530]

### 堆排序 ###

**描述**

堆是一个数组，它可以看作是一个完全二叉树，一般来说在堆排序算法中，我们常用最大堆（即每个根节点都比它的两个孩子的值要大）。最小堆用来进行优先队列中。

**步骤**

*  建立一个最大堆，要根据最大堆的性质维护一个堆。
 *  从根节点开始，将每个节点和最后一个节点替换，使用一个变量控制堆的大小。
 *  替换的同时也要继续维持堆的性质。
 *  最后得出的数组的顺序，便是排好序的数组。

**代码**

package DS_Sort_heap;
    
    import java.util.Arrays;
    
    /** * Created by 张超帅 on 2018/10/27. */
    public class heap { 
    
    
        public static void sort(int[] a) { 
            int len = a.length - 1;
            for(int i = len / 2; i >= 0; i --) { 
                sink(a, i, len);
            }
            while(len > 0) { 
                exch(a, 0, len -- );
                sink(a, 0, len);
            }
        }
    	public static void sink(int[] a, int k, int len ) { 
    		while(k * 2  + 1< len) { 
    			int j = k * 2 + 1;
    			if(a[k] < a[j+1]) j ++;
    			if(less(a[k], a[i])) break;
    			exch(a, k, j);
    			k = j;
    		}
    	}
        public static Boolean less(int x, int y) { 
            return x < y ? true : false;
        }
        public static void exch(int[] a, int x, int y) { 
            int temp = a[x];
            a[x] = a[y];
            a[y] = temp;
        }
        public static void main(String[] args) { 
            int a[] = { 9,6,3,1,-4,-5,-9};
            System.out.println("排序前的数组： " + Arrays.toString(a));
            sort(a);
            System.out.println("排序前的数组： " + Arrays.toString(a));
        }
    }

**复杂度分析**

*  时间复杂度：O(Nlog(N))
 *  空间复杂度：O(1)

### 归并排序 ###

**描述**

采用分治的思想，将大的问题划分为小的子问题，大部分采用递归的策略；将其以递归的形式划分为多个单个对的数进行对比，依次进行向上的合并，在合并过程中需要借助其他的数组进行合并，可以是一个新数组，也可以是两个新数组。

**步骤**

*  将数组按照二分策略进行递归。
 *  将其进行合并，分配一个新的并且和原始数组相同大小的数组。
 *  将新的数组分成一半，进行比较，小的将其依次放入原始的数组。
 *  递归结束后，原始的数组也就排好序了。

**代码**

package DS_Sort_Merge;
    
    import java.util.Arrays;
    
    /** * Created by 张超帅 on 2018/10/21. */
    public class Merge { 
    
    
        private static int[] aux ;
        public static void sort(int[] a) { 
            int len = a.length;
            aux = new int[len];
            sort(a, 0, len - 1);
    
        }
        public static void sort(int[] a, int ho, int hi) { 
            if(ho >= hi) return ;
            int mid = ho + (hi - ho) / 2;
            sort(a, ho, mid);
            sort(a, mid + 1, hi);
            subMerge(a, ho, mid, hi);
        }
        public static void subMerge(int[] a, int ho, int mid, int hi) { 
            System.arraycopy(a, ho, aux, ho, hi - ho + 1 );
            int i = ho, j = mid + 1;
            for(int k = ho; k <= hi; k ++) { 
                if(i > mid) { 
                    a[k] = aux[j++];
                }else if(j > hi) { 
                    a[k] = aux[i++];
                }else if (a[i] < a[j]) { 
                    a[k] = aux[i++];
                }else { 
                    a[k] = aux[j++];
                }
            }
        }
        public static void main(String[] args) { 
            int[] a= { 1,4,6,3,2,4,7,0,-1};
            System.out.println("排序前的数组： " + Arrays.toString(a));
            sort(a);
            System.out.println("排序后的数组： " + Arrays.toString(a));
        }
    }

**结果**

排序前的数组： [1, 4, 6, 3, 2, 4, 7, 0, -1]
    排序后的数组： [-1, 1, 2, 4, 4, 0, 3, 6, 7]

**复杂度分析**

*  时间复杂度： O(Nlog(N))
 *  空间复杂度： O(log(N)) ~O(N)

### 快速排序 ###

**描述**

该算法的关键点在于切分，利用切分，将其大于`该点`(即每次进行递归的第一个点)的数值放到右边，小于该点的数值放到左边，利用递归，递归左边和右边，最终得到的数组便是有序的数组。

package DS_Sort_quick;
    
    import java.util.Arrays;
    
    /** * Created by 张超帅 on 2018/10/21. */
    public class Quick { 
    
        public static void sort(int[] a) { 
            sort(a, 0, a.length - 1);
            return ;
        }
        public static void sort(int[] a, int ho, int hi) { 
            if(ho >= hi) return;
            int j = parition(a, ho, hi);
            sort(a, ho, j - 1);
            sort(a, j + 1, hi);
            return;
        }
        public static int parition(int[] a, int ho, int hi) { 
            int v = ho, i = ho, j = hi + 1;
            while(true) { 
                while(a[++i] < a[v]) if(i == hi)break;
                while(a[--j] > a[v]) if(j == ho)break;
                if(i >= j) break;
                exch(a, i, j);
            }
            exch(a, v, j);
            return j;
        }
        public static void exch(int[] a, int x, int y) { 
            int temp = a[x];
            a[x] = a[y];
            a[y] = temp;
        }
        public static void main(String[] args) { 
            int[] a = { 0, 3, 2, 4 , 7, 9, 1, 0, 23, 16, -3, -5};
            System.out.println("排序前的数组： " + Arrays.toString(a));
            sort(a);
            System.out.println("排序后的数组; " + Arrays.toString(a));
        }
    }

**复杂度分析**

*  时间复杂度： O（Nlog(N)）
 *  空间复杂度： O（log（N））

### 三路快排 ###

**描述**

基于快速排序的思路之上，将其分为三个区间，第一个区间是小于v，第二个区间等于v，第三个区间大于v的，利用递归，再进行切分，最终得到的数组便是排好序的数组。

package DS_Sort_quick3way;
    
    import java.util.Arrays;
    
    /** * Created by 张超帅 on 2018/10/21. */
    public class Quick3way { 
        public static void sort(int[] a) { 
            sort(a, 0, a.length - 1);
        }
        public static void sort(int[] a, int ho, int hi) { 
            if(ho >= hi) return;
            int v = a[ho];
            int i = ho + 1, gt = hi , lt = ho;
            while(i <= gt) { 
                int cmp = compareTo(a[i], v);
                if(cmp < 0){  exch(a, i++, lt ++);}
                else if(cmp > 0) { exch(a, i, gt --);}
                else { 
                    i++;
                }
            }
            sort(a, ho, lt - 1);
            sort(a, gt + 1, hi);
        }
        public static void exch(int[] a, int x, int y) { 
            int temp = a[x];
            a[x] = a[y];
            a[y] = temp;
        }
        public static int compareTo(int x, int y) { 
            return x - y;
        }
        public static void main(String[] args) { 
            int[] a = { 0, 3, 2, 4 , 7, 9, 1, 0, 23, 16,-45};
            System.out.println("排序前的数组 : " + Arrays.toString(a));
            sort(a);
            System.out.println("排序后的数组： " + Arrays.toString(a));
    
        }
    }