Java数据结构的十大排序

目录

• 1.直接插入排序
• 1.1 动图演示
• 1.2 插入排序的思路
• 1.3 代码实现
• 1.4 性能分析
• 2.希尔排序
• 2.1 原理
• 2.2 动图演示
• 2.3 代码实现
• 2.4 性能分析
• 3.直接选择排序
• 3.1 动图演示
• 3.2 代码实现
• 3.3 性能分析
• 4.堆排序
• 4.1 动图演示
• 4.2 代码实现
• 4.3 性能分析
• 5.冒泡排序
• 5.1 动图演示
• 5.2 代码实现
• 5.3 性能分析
• 6.快速排序
• 6.1 原理
• 6.2 动图演示
• 6.3 实现方法
• 6.3.1 Hoare法
• 6.3.2 挖坑法
• 6.4 代码实现
• 6.5 快排优化
• 6.5.1 三数取中法
• 6.5.2 加上直接插入排序
• 6.6 非递归的实现
• 6.6.1 非递归思路
• 6.6.2 非递归代码实现
• 6.7 性能分析
• 7.归并排序
• 7.1 原理
• 7.2 动图演示
• 7.3 代码实现—递归
• 7.4 代码实现—非递归
• 7.5 性能分析
• 8.计数排序
• 8.1 算法的步骤
• 8.2 动图演示
• 8.3 代码实现
• 8.4 性能分析
• 9.桶排序
• 9.1 原理
• 9.2 算法的步骤
• 9.3 画图解析
• 9.4 代码实现
• 9.5 性能分析
• 10.基数排序
• 10.1 算法的步骤
• 10.2 动图演示
• 10.3 代码实现
• 10.4 性能分析

1.直接插入排序

1.1 动图演示

1.2 插入排序的思路

1. 从第一个元素开始,这里我们第一个元素是已排序的.
2. 取下一个元素,和有序序列的元素从后往前比较.( 有序区间 : [0,i) )
3. 如果得到的有序序列的元素 比 该元素大 则 将取得的有序元素往后放
4. 重复3操作,直到得到的有序元素 比 该元素小, 或者 有序元素比完了.记录这个位置
5. 然后将该元素放入到这个位置.
6. 遍历数组,重复2~5的操作.

1.3 代码实现

   /**
     * 时间复杂度:
     *      最好的情况: O(n)
     *      最坏的情况: O(n^2)
     * 空间复杂度: O(1)
     * @param array
     */
    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int j = i - 1;
            int tmp = array[i];
            while (j >= 0) {
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                    j--;
                }else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }

1.4 性能分析

时间复杂度(平均)	时间复杂度(最坏)	时间复杂度(最好)	空间复杂度	稳定性
O(n^2)	O(n^2)	O(n)	O(1)	稳定

插入排序，初始数据越接近有序，时间效率越高。

2.希尔排序

2.1 原理

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数gap，把待排序文件中所有记录分成个gap组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后，取gap = (gap/3)+1，重复上述分组和排序的工作。当到达gap=1时，所有记录在统一组内排好序。

• 希尔排序是对直接插入排序的优化。
• 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

2.2 动图演示

2.3 代码实现

    /**
     *
      * @param array 排序的数组
     * @param gap 每组的间隔 -> 数组
     */
     public static void shell(int[] array,int gap){
         for (int i = gap; i < array.length ; i++) {
             int tmp = array[i];
             int j = i - gap;
             while(j>=0){
                 if(array[j] > tmp){
                     array[j + gap] = array[j];
                     j -= gap;
                 }else {
                     break;
                 }
             }
             array[j + gap] = tmp;
         }
     }

     public static void shellSort(int[] array){
         int gap = array.length;
         while (gap > 1){
             gap = (gap / 3) + 1;// +1 保证最后一个序列是 1 (除几都行)
             shell(array,gap);
         }
     }

2.4 性能分析

时间复杂度(平均)	时间复杂度(最坏)	时间复杂度(最好)	空间复杂度	稳定性
O(n^1.3)	O(n^2)	O(n)	O(1)	不稳定

3.直接选择排序

3.1 动图演示

3.2 代码实现

 /**
     * 时间复杂度:
     *      最好: O(n^2)
     *      最坏: O(n^2)
     * 空间复杂度: O(1)
     * 稳定性: 不稳定
     * @param array
     */
    public static void selectSort(int[] array){
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = i + 1; j <array.length ; j++) {
                if(array[j] < array[i]){
                    int tmp = array[i];
                    array[i] = array[j];
                    array[j] = tmp;
                }
            }
        }
    }

3.3 性能分析

时间复杂度(平均)	时间复杂度(最坏)	时间复杂度(最好)	空间复杂度	稳定性
O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定

4.堆排序

4.1 动图演示

4.2 代码实现

    public static void siftDown(int[] array,int root, int len){
        int parent = root;
        int child = root * 2 + 1;
        while (child < len){
            if( child+1 < len && array[child] < array[child+1] ){
                child++;
            }
            //这里child下标就是左右孩子的最大值的下标
            if(array[child] > array[parent]){
                int tmp = array[child];
                array[child] = array[parent];
                array[parent] = tmp;
                parent = child;
                child = parent * 2 + 1;
            }else {
                break;
            }
        }
    }

    public static void createHeap(int[] array){
        for (int i = (array.length - 1 - 1) / 2; i >= 0; i++) {
            siftDown(array,i,array.length);
        }
    }
    public static void heapSort(int[] array){
        createHeap(array);
        int end = array.length - 1;
        while (end > 0){
            int tmp = array[end];
            array[end] = array[0];
            array[0] =tmp;
            siftDown(array,0,end);
            end--;
        }
    }

4.3 性能分析

时间复杂度(平均)	时间复杂度(最坏)	时间复杂度(最好)	空间复杂度	稳定性
O(n * log(n))	O(n * log(n))	O(n * log(n))	O(1)	不稳定

5.冒泡排序

5.1 动图演示

5.2 代码实现

public static void BubbleSort(int[] array){
        for (int i = 0; i < array.length - 1; i++) {
            boolean flg = false;
            for (int j = 0; j < array.length - 1 - i ; j++) {
                if(array[j+1] < array[j]){
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    flg = true;
                }
            }
            if(!flg){
                break;
            }
        }
    }

5.3 性能分析

时间复杂度(平均)	时间复杂度(最坏)	时间复杂度(最好)	空间复杂度	稳定性
O(n^2)	O(n^2)	O(n)	O(1)	稳定

6.快速排序

6.1 原理

• 从待排序区间选择一个数，作为基准值(pivot)；
• Partition: 遍历整个待排序区间，将比基准值小的（可以包含相等的）放到基准值的左边，将比基准值大的（可以包含相等的）放到基准值的右边；
• 采用分治思想，对左右两个小区间按照同样的方式处理，直到小区间的长度 == 1，代表已经有序，或者小区间的长度 == 0，代表没有数据。

6.2 动图演示

6.3 实现方法

6.3.1 Hoare法

6.3.2 挖坑法

6.4 代码实现

  //Hoare法
    public static void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    public static int partition1(int[] array,int low,int high) {
        int i = low;
        int tmp = array[low];
        while (low < high){
            while (low < high && array[high] >= tmp){
                high--;
            }
            while (low < high && array[low] <= tmp){
                low++;
            }
            swap(array,low,high);
        }
        swap(array,i,low);
        return low;
    }

    //挖坑法
    public static int partition2(int[] array,int low,int high) {
        int tmp = array[low];

        while (low < high){
            while (low < high && array[high] >= tmp){
                high--;
            }
            array[low] = array[high];
            while (low < high && array[low] <= tmp){
                low++;
            }
            array[high] = array[low];
        }
        array[low] = tmp;
        return low;
    }

    public static void quick(int[] array,int start,int end){
        if(start >= end) return;
        int pivot = partition1(array,start,end);

        quick(array,start,pivot-1);

        quick(array,pivot+1,end);
    }
    public static void quickSort(int[] array){
        quick(array,0,array.length-1);
    }

6.5 快排优化

6.5.1 三数取中法

   public static void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
        public static int partition2(int[] array,int low,int high) {
        int tmp = array[low];

        while (low < high){
            while (low < high && array[high] >= tmp){
                high--;
            }
            array[low] = array[high];
            while (low < high && array[low] <= tmp){
                low++;
            }
            array[high] = array[low];
        }
        array[low] = tmp;
        return low;
    }
    public static void selectPivotMedianOFThree(int[] array,int start,int end,int mid){
        if(array[mid] > array[start]){
            swap(array,start,mid);
        }//此时mid下标的值肯定小于start下标的值 array[mid] <= array[start]
        if(array[mid] > array[end]){
            swap(array,mid,end);
        }//此时mid下标的值肯定小于end下标的值 array[mid] <= array[end]
        if(array[start] > array[end]){
            swap(array,start,end);
        }//此时有 array[mid] <= array[start] <= array[end]
    }

    public static void quick1(int[] array,int start,int end){
        if(start >= end) return;
        int mid = (start + end) / 2;
        selectPivotMedianOFThree(array,start,end,mid);

        int pivot = partition2(array,start,end);

        quick1(array,start,pivot-1);

        quick1(array,pivot+1,end);
    }

    public static void quick1Sort(int[] array){
        quick1(array,0,array.length - 1);
    }

6.5.2 加上直接插入排序

    public static void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    public static void insertSort2(int[] array,int start,int end){
        for (int i = start + 1; i <= end; i++) {
            int j = i + 1;
            int tmp = array[i];
            while (j >= 0){
                if(array[j] > tmp){
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
        public static int partition2(int[] array,int low,int high) {
        int tmp = array[low];

        while (low < high){
            while (low < high && array[high] >= tmp){
                high--;
            }
            array[low] = array[high];
            while (low < high && array[low] <= tmp){
                low++;
            }
            array[high] = array[low];
        }
        array[low] = tmp;
        return low;
    }
        public static void selectPivotMedianOFThree(int[] array,int start,int end,int mid){
        if(array[mid] > array[start]){
            swap(array,start,mid);
        }//此时mid下标的值肯定小于start下标的值 array[mid] <= array[start]
        if(array[mid] > array[end]){
            swap(array,mid,end);
        }//此时mid下标的值肯定小于end下标的值 array[mid] <= array[end]
        if(array[start] > array[end]){
            swap(array,start,end);
        }//此时有 array[mid] <= array[start] <= array[end]
    }

    public static void quick2(int[] array,int start,int end){
        if(start >= end) return;
        if(end - start + 1 <= 100){
            insertSort2(array,start,end);
            return;
        }
        int mid = (start + end)/2;
        selectPivotMedianOFThree(array,start,end,mid);

        int pivot = partition2(array,start,end);
        quick2(array,start,pivot-1);
        quick2(array,pivot+1,end);
    }    
    public static void quick2Sort(int[] array){
        quick2(array,0,array.length - 1);
    }

6.6 非递归的实现

6.6.1 非递归思路

• 首先调用partition,找到pivot
• 然后把pivot的 左区间 和 右区间 的下标放到栈立马
• 判断栈是否为空,不为空,弹出栈顶的2个元素(注意:入栈的顺序 决定了出栈的顺序中的第一个元素是high的还是low的)
• 然后再进行调用partition,找pivot,
• 重复以上操作.

6.6.2 非递归代码实现

  public static void quickSort4(int[] array){
        Stack<Integer> stack = new Stack<>();
        int low = 0;
        int high = array.length - 1;

        int pivot = partition2(array,low ,high);
        //左边有2个元素即以上
        if(pivot > low + 1){
            stack.push(0);
            stack.push(pivot - 1);
        }
        //右边有2个元素即以上
        if(pivot < high - 1){
            stack.push(pivot + 1);
            stack.push(high);
        }
        while (!stack.isEmpty()){
            high = stack.pop();
            low = stack.pop();
            pivot = partition2(array,low,high);
            //左边有2个元素即以上
            if(pivot > low + 1){
                stack.push(0);
                stack.push(pivot - 1);
            }
            //右边有2个元素即以上
            if(pivot < high - 1){
                stack.push(pivot + 1);
                stack.push(high);
            }
        }
    }

6.7 性能分析

时间复杂度(平均)	时间复杂度(最坏)	时间复杂度(最好)	空间复杂度	稳定性
O(n * log(n))	O(n^2)	O(n * log(n))	O(log(n))~O(n)	不稳定

7.归并排序

7.1 原理

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子 序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

7.2 动图演示

7.3 代码实现—递归

    public static void merge(int[] array,int low ,int high ,int mid){
        int s1 = low;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = high;

        int[] tmp = new int[high - low + 1];
        int k = 0;

        while (s1 <= e1 && s2 <= e2){
            if(array[s1] <= array[s2]){
                tmp[k++] = array[s1++];
            }else {
                tmp[k++] = array[s2++];
            }
        }
        while (s1 <= e1){
            tmp[k++] = array[s1++];
        }
        while (s2 <= e2){
            tmp[k++] = array[s2++];
        }

        for (int i = 0; i < tmp.length; i++) {
            array[i+low] = tmp[i];
        }
    }
    public static void mergeSortInternal(int[] array,int low ,int high){
        if(low >= high) return;
        int mid = (low + high) / 2;
        mergeSortInternal(array,low,mid);
        mergeSortInternal(array,mid+1,high);

        merge(array,low,high,mid);
    }

    public static void mergeSort(int[] array){
        mergeSortInternal(array,0,array.length - 1);
    }

7.4 代码实现—非递归

    public static void merge1(int[] array,int gap){
        int[] tmp = new int[array.length];
        int k = 0;

        int s1 = 0;
        int e1 = s1 + gap - 1;

        int s2 = e1 + 1;
        int e2 = s2 + gap - 1 > array.length ? array.length - 1 : s2 + gap - 1;

        while (s2 < array.length){
            while (s1 <= e1 && s2 <= e2){
                if(array[s1] <= array[s2]){
                    tmp[k++] = array[s1++];
                }else {
                    tmp[k++] = array[s2++];
                }
            }
            while (s1 <= e1){
                tmp[k++] = array[s1++];
            }
            while (s2 <= e2){
                tmp[k++] = array[s2++];
            }

            s1 = e2 + 1;
            e1 = s1 + gap - 1;

            s2 = e1 + 1;
            e2 = s2 + gap - 1 > array.length ? array.length - 1 : s2 + gap - 1;
        }

        while (s1 <= array.length - 1){
            tmp[k++] = array[s1++];
        }

        for (int i = 0; i < tmp.length; i++) {
            array[i] = tmp[i];
        }
    }

    public static void mergeSort1(int[] array){
        for (int i = 1; i < array.length; i*=2) {
            merge1(array,i);
        }
    }

7.5 性能分析

时间复杂度(平均)	时间复杂度(最坏)	时间复杂度(最好)	空间复杂度	稳定性
O(n * log(n))	O(n * log(n))	O(n * log(n))	O(n)	稳定

8.计数排序

当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。

8.1 算法的步骤

（1）找出待排序的数组中最大和最小的元素
（2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项
（3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
（4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

8.2 动图演示

8.3 代码实现

    public static void CountingSort(int[] array){
        int maxValue = GetMaxValue(array);
        int bucketLen = maxValue + 1;
        int[] bucket = new int[bucketLen];
        for (int value:array) {
            bucket[value]++;
        }
        int index = 0 ;

        for (int i = 0; i < bucketLen; i++) {
            while(bucket[i] > 0){
                array[index++] = i;
                bucket[i]--;
            }
        }
    }

    public static int GetMaxValue(int[] array){
        int maxValue = array[0];
        for (int i = 0; i < array.length; i++) {
            if(maxValue < array[i]){
                maxValue = array[i];
            }
        }
        return maxValue;
    }

8.4 性能分析

时间复杂度(平均)	时间复杂度(最坏)	时间复杂度(最好)	空间复杂度	稳定性
O(n+k)	O(n+k)	O(n+k)	O(k)	稳定

9.桶排序

9.1 原理

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

为了使桶排序更加高效，我们需要做到这两点：

• 在额外空间充足的情况下，尽量增大桶的数量
• 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

9.2 算法的步骤

• 设置一个定量的数组当作空桶；
• 遍历输入数据，并且把数据一个一个放到对应的桶里去；
• 对每个不是空的桶进行排序；
• 从不是空的桶里把排好序的数据拼接起来。

9.3 画图解析

9.4 代码实现

 public static void bucketSort(int[] arr) {
        if (arr.length == 0) {
            return;
        }

        int minValue = arr[0];
        int maxValue = arr[0];
        for (int value : arr) {
            if (value < minValue) {
                minValue = value;
            } else if (value > maxValue) {
                maxValue = value;
            }
        }
        //得到最大和最小元素

        int bucketNum = (maxValue - minValue) / arr.length + 1;//桶的数量
        ArrayList<ArrayList<Integer>> bucket = new ArrayList<>(bucketNum);
        for (int i = 0; i < bucketNum; i++) {
            bucket.add(new ArrayList<>());
        }
        
        //将元素放入到桶中
        for (int i = 0; i < arr.length; i++) {
            int num = (arr[i] - minValue) / arr.length;
            bucket.get(num).add(arr[i]);
        }

        for (int i = 0; i < bucket.size(); i++) {
            //这里是比较,可以选择其他的方式实现,这里为了演示采取Collection的sort
            Collections.sort(bucket.get(i));
        }

        // 将桶中的元素赋值到原序列
        int index = 0;
        for(int i = 0; i < bucket.size(); i++){
            for(int j = 0; j < bucket.get(i).size(); j++){
                arr[index++] = bucket.get(i).get(j);
            }
        }
    }

9.5 性能分析

时间复杂度(平均)	时间复杂度(最坏)	时间复杂度(最好)	空间复杂度	稳定性
O(n+k)	O(n^2)	O(n+k)	O(n+k)	稳定

10.基数排序

10.1 算法的步骤

• 取得数组中的最大数，并取得位数；
• arr为原始数组，从最低位开始取每个位组成radix数组；
• 对radix进行计数排序（利用计数排序适用于小范围数的特点）

10.2 动图演示

10.3 代码实现

    public static int getNumLength(int num){
        if(num == 0) return 1;
        int count = 0;
        for (int i = num; i != 0; i /= 10) {
            count++;
        }
        return count;
    }
    public static void RadixSort(int[] array){
        int maxValue = array[0];
        for (int i = 0; i < array.length; i++) {
            if(maxValue < array[i]){
                maxValue = array[i];
            }
        }
        int maxDigit = getNumLength(maxValue);

        int mod = 10;
        int dev = 1;
        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
            int[][] counter = new int[mod * 2][0];

            for (int j = 0; j < array.length; j++) {
                int bucket = ((array[j] % mod) / dev) + mod;
                counter[bucket] = arrayAppend(counter[bucket], array[j]);
            }

            int pos = 0;
            for (int[] bucket : counter) {
                for (int value : bucket) {
                    array[pos++] = value;
                }
            }
        }

    }
    public static int[] arrayAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }

10.4 性能分析

时间复杂度(平均)	时间复杂度(最坏)	时间复杂度(最好)	空间复杂度	稳定性
O(n*k)	O(n*2)	O(n*k)	O(n+k)	稳定

总结：

到此这篇关于 Java数据结构的十大排序的文章就介绍到这了,更多相关 Java数据结构十大排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！