Sort Algorithms

算法
字数统计: 2.2k   |   阅读时长≈ 10 分钟

概述：本文主要记录了八大排序算法的Java实现

部分性能总结

冒泡排序

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
package com.zzzzzq.sort;

import java.util.Arrays;

/**
 * 冒泡排序
 *
 * 步骤：
 * 1. 比较相邻的元素，如果第一个比第二个大，就交换他们两个
 * 2. 对每一对相邻元素作同样的工作，每经过一次循环，会有一个最大的元素移到数组后段
 * 3. 重复上述循环直到没有任何一对数字需要比较
 *
 * 时间复杂度O(n^2), 空间复杂度O(1)
 * 稳定
 */
public class Bubble {
    public static void bubbleSort(int[] arr){
        int n = arr.length;
        for(int i = 0; i != n; ++i) {
            for (int j = 0; j < n - 1 - i; ++j) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        System.out.println("arr = " + Arrays.toString(arr));
    }
}

插入排序

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
package com.zzzzzq.sort;

import java.util.Arrays;

/**
 * 插入排序
 *
 * 1. 从第一个元素开始
 * 2. 取出下一个元素，在已经排序好的元素序列中从后向前扫描
 * 3. 如果已排序的元素大于新元素，则两两交换
 * 4. 如果扫描到的已排序的元素小于新元素，则视为找到了"插入位置"，这个元素已经完成排序
 * 5. 重复步骤2，3，4
 *
 * 时间复杂度O(n^2),空间复杂度O(1)
 * 稳定
 */
public class Insertion {
    public static void insertionSort(int[] arr){
        int n = arr.length;
        for(int i = 1; i < n; ++i){
            for(int j = i-1 ; j >= 0; --j){
                if(arr[j]>arr[i]){
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
                else{
                    break;
                }
            }
        }
        System.out.println("arr = " + Arrays.toString(arr));;
    }
}

希尔排序

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
package com.zzzzzq.sort;

import com.sun.xml.internal.ws.api.model.wsdl.WSDLOutput;

import java.util.Arrays;

/**
 * 希尔排序(又称递减增量排序算法)
 * 是简单插入排序的改进版，会有限比较距离较远的元素
 *
 * 步骤：
 * 1. 设置一个增量序列t1, t2, ... tk,我的设置一般为t1 = n/3 +1 , tn = tn-1/3 +1
 * 2. 按增量序列个数k面对序列进行k趟排序
 *
 */
public class Shell {
    public static void shellSort(int[] arr){
        int n = arr.length;
        int h = 1;
        while(h<n/3) h = 3 * h + 1;

        while(h>1){
            //h-sort the array
            for(int i = h; i < n;i ++){
                for(int j=i;j>=h && arr[j]<arr[j-h]; j-=h){
                    exch(arr[j],arr[j-h]);
                }
            }
            h/=3;
        }
        System.out.println("arr = " + Arrays.toString(arr));
    }

    public static void exch(int a, int b){
        int temp = a;
        a=b;
        b=temp;
    }

}

选择排序

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
package com.zzzzzq.sort;

import java.util.Arrays;

/**
 * 选择排序
 *
 * 1. 从待排序序列中找到最小的元素
 * 2. 将该元素与待排序序列的第一个元素进行交换
 * 3. 从余下的N-1个元素中找出关键字最小的元素，重复1.2两步，直到排序结束
 *
 * 时间复杂度O(n^2),空间复杂度O(n)
 * 不稳定
 */
public class Selection {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for(int i = 0; i!= n; ++i){
            int minindex = i;
            for(int j=i; j != n; ++j){
                if(arr[j]<arr[minindex]){
                    minindex=j;
                }
            }
            if(minindex!=i){
                int temp = arr[i];
                arr[i] = arr[minindex];
                arr[minindex] = arr[i];
            }
        }
        System.out.println("arr = " + Arrays.toString(arr));
    }
}

堆排序

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
52
53
54
55
56
57
58
package com.zzzzzq.sort;

import java.util.Arrays;

/**
 * 堆排序
 * 基本思想：堆排序的过程就是将待排序的序列构造成一个堆，选出堆中最大的移走
 * 再把剩余的元素调整成堆，找出最大的再移走，重复直至有序
 *
 * 步骤:
 * 1. 先将初始序列构造成一个大根堆，此时第一个元素最大，此堆为初始的无序区
 * 2. 将堆顶元素(最大元素)和无序区的最后一个元素交换，并进行调整
 * 3. 重复步骤2直到无序区只有一个元素时停止
 *
 * 需要定义如下几种操作:
 * 1. 最大堆调整(Max_Heapify): 将堆的末端子节点作调整，使得子节点永远小于父节点
 * 2. 创建最大堆(Build_Max_Heap): 将堆所有数据重新排序
 * 3. 堆排序(HeapSort): 移除位在第一个数据的根节点，并做最大堆调整的递归运算
 *
 * 用数组表示堆，对于节点的访问:
 * 1. 父节点 i 的左子节点在位置 (2*i+1)
 * 2. 父节点 i 的左子节点在位置 (2*i+2)
 * 3. 子节点 j 的父节点在位置 floor((i-1)/2)
 *
 * 时间复杂度O(nlogn),空间复杂度O(n)
 * 稳定
 */
public class Heap {
    public static void heapSort(int[] arr){
        for(int i=arr.length;i>0;--i){
            max_heapify(arr,i);
            //将堆中最大的元素放到末尾
            exch(arr[0],arr[i-1]);
        }
        System.out.println("arr = " + Arrays.toString(arr));
    }

    private static void max_heapify(int[] arr, int limit){
        if(arr.length <= 0 || arr.length < limit) return;

        int parentIdx = limit / 2;
        for(; parentIdx>=0;parentIdx--){
            if(parentIdx*2>=limit) continue;
            int left = parentIdx*2;
            int right = (left+1) >= limit ? left : left+1;

            int maxChildId = arr[left] >= arr[right] ? left : right;
            if(arr[maxChildId] > arr[parentIdx]){
                exch(arr[maxChildId],arr[parentIdx]);
            }
        }
    }
    private static void exch(int a, int b){
        int temp = a;
        a=b;
        b=temp;
    }
}

快速排序

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
package com.zzzzzq.sort;

import java.util.Arrays;

/**
 * 快速排序
 *
 * 步骤：
 * 1. 从数列中挑出一个元素，称为pivot
 * 2. 重新排列数组，所有比pivot小的元素摆放在基准前面，所有比pivot大的元素摆在基准的后面
 * 3. "递归地"把小于pivot的子数列和大于pivot的子数列排序
 */
public class Quick {
    public static void quickSort(int[] arr){
        quickSort(arr,0,arr.length-1);
        System.out.println("arr = " + Arrays.toString(arr));
    }
    private static void quickSort(int[] arr,int low, int high){
        if(low > high) return;
        int index = partition(arr,low,high);
        quickSort(arr,low,index-1);
        quickSort(arr,index+1,high);
    }
    private static int partition(int[] arr, int low, int high){
        int pivot = arr[low];
        while(low < high){
            while(low < high && arr[high] >= pivot){
                --high;
            }
            arr[low] = arr[high];
            while(low < high && arr[low] <= pivot){
                ++low;
            }
            arr[high] = arr[low];
        }
        arr[high] = pivot;
        return high;
    }
}

归并排序

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
package com.zzzzzq.sort;

import java.util.Arrays;

/**
 * 归并排序
 *
 * 步骤:
 * 1. 将序列每相邻两个数字进行归并操作，形成floor(n/2)个序列，排序后每个序列包含两个元素；
 * 2. 将上述序列再次合并，形成floor(n/4)个序列，每个序列包含四个元素
 * 3. 重复步骤2，直到所有元素排序完毕
 */
public class Merge {
    public static void mergeSort(int[] arr){
        int[] aux = new int[arr.length];
        mergeSort(arr,aux,0,arr.length-1);
        System.out.println("arr = " + Arrays.toString(arr));
    }
    private static void mergeSort(int[] arr,int[] aux, int low, int high){
        if(high <= low) return;
        int mid = low + ( high - low ) / 2;
        //优化方案，将mergeSort中aux,arr互换可以节省拷贝到辅助数组的时间，但不能节省空间
        mergeSort(arr, aux, low, mid);
        mergeSort(arr, aux, mid+1, high);
        //优化方案，若a[mid]<a[mid+1]，则表示两边已经有序，不需要merge，直接return
        if(arr[mid]<arr[mid+1]){
            merge(arr, aux, low, mid, high);
        }
    }
    private static void merge(int[] arr, int[] aux, int low, int mid, int high){
        //copy
        if (high + 1 - low >= 0) System.arraycopy(arr, low, aux, low, high + 1 - low);
        //merge
        int i = low, j = mid + 1;
        for(int k = low; k <= high ;++k){
            if(i > mid)             arr[k] = aux[j++];
            else if(j > high)       arr[k] = aux[i++];
            else if(aux[j]<aux[i])  arr[k] = aux[j++];
            else                    arr[k] = aux[i++];
        }
    }
}

桶排序

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
package com.zzzzzq.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

/**
 * 桶排序
 * 基本思想：把数组arr划分为n个大小相同子区间(桶)，每个子区间各自排序，最后合并
 *
 * 1. 找出待排序数组中的最大值max，最小值min
 * 2. 使用动态数组ArrayList作为桶，桶里放的元素也用ArrayList存储。桶的数量为(max-min)/arr.length+1
 * 3. 遍历数组arr，计算每个元素arr[i]放的痛
 * 4. 每个桶各自排序
 * 5. 遍历桶数组，把排序号的元素放进输出数组
 */
public class Bucket {
    public static void bucketSort(int[] arr){
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i = 0;i != arr.length; ++i){
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }

        //桶数
        int bucketNum = (max - min) / arr.length + 1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
        for(int i = 0; i != bucketNum; ++i){
            bucketArr.add(new ArrayList<Integer>());
        }

        //将每个元素放入桶中
        for(int i = 0; i != arr.length; ++i){
            int num = (arr[i] - min) / (arr.length);
            bucketArr.get(num).add(arr[i]);
        }

        //堆每个桶进行排序并修改原数组
        int index = 0;
        for(int i = 0; i != bucketNum; ++i){
            Collections.sort(bucketArr.get(i));
            for(int j = 0; j != bucketArr.get(i).size(); ++j){
                arr[index] = bucketArr.get(i).get(j);
                ++index;
            }
        }
        System.out.println("arr = " + Arrays.toString(arr));
    }
}

测试模块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package test;

import com.zzzzzq.sort.Bubble;
import com.zzzzzq.sort.Bucket;
import com.zzzzzq.sort.Heap;
import com.zzzzzq.sort.Insertion;
import com.zzzzzq.sort.Merge;
import com.zzzzzq.sort.Quick;
import com.zzzzzq.sort.Selection;
import com.zzzzzq.sort.Shell;

public class Test {
    public static void main(String[] args) {
        int[] arr = new int[]{0, 4, 5, 2, 1, 7, 10, 9, 6,34,32,44,3,8,23};
        Bubble.bubbleSort(arr);
        Selection.selectionSort(arr);
        Insertion.insertionSort(arr);
        Shell.shellSort(arr);
        Heap.heapSort(arr);
        Quick.quickSort(arr);
        Merge.mergeSort(arr);
        Bucket.bucketSort(arr);
    }
}
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2022 ZHU
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信