排序算法及java实现

简介

排序算是非常基础的算法，为什么我们需要排序算法呢？假设我们只有10个数，或者100个数，其实根本不需要研究这么多的排序算法，正常我们会使用的插入排序或者选择排序足够了，没必要发明快排，基数排序这些。
只有将需要排序的量非常大，我们才开始需要一些效率更高，更合适的排序算法。看一下常见的几种排序算法的效率：

来解释一下稳定性的意思，稳定性的意思是说，相等的数在排序后仍然保持排序前的相对顺序。

贴一个百科的解释：
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
然后我们来看具体的算法

注意：排序算法的速度是有极限的，基于比较的排序算法的最优下界是$O(nlogn)$，至于为什么，我还没搞明白，可以看看这个：CBA理论, 为什么基于比较的排序方法的性能极限是O(nlogn)

冒泡排序

一般我们提起冒泡排序，都说它是最简单的排序，但是对我来说，实际生活中，我感觉使用插入排序或者选择排序其实更多，很少会直接想到冒泡排序，冒泡排序的操作过程就是，从第一个起，和后面的两两对比，然后如果后面的小于前面的，就进行交换，如此这般，循环直到所有数字顺序都正确。

/**
 * 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
 * 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
 * 针对所有的元素重复以上的步骤，除了最后一个。
 * 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
 */
public class BubbleSort {

    public static void main(String[] args) {
        int[] list= {81,94,11,96,12,35,17,95,28,58,41,75,15};
        System.out.println("排序前： "+ Arrays.toString(list));

        int count=13;
        bubbleSort(list,count);
        System.out.println("排序后： "+ Arrays.toString(list));
    }

    private static void bubbleSort(int[] list, int count) {
        for (int i = list.length-1; i >0 ; i--) {
            boolean flag=true;

            for (int j = 0; j < i; j++) {
                if (list[j]>list[j+1]){
                    flag=false;
                    int temp=list[j];
                    list[j]=list[j+1];
                    list[j+1]=temp;
                }
            }

            if (flag){
                return;
            }
        }

    }
}
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

插入排序

插入排序就是，从第一个开始就当它有序，开始和后面的进行对比，当发现大小小于前面的时候，就一直找到对的位置放下这个数字。

/**
 *插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
 *插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。
 */
public class InsertionSort {

    public static void main(String[] args) {
        int[] list= {81,94,11,96,12,35,17,95,28,58,41,75,15};
        System.out.println("排序前： "+ Arrays.toString(list));

        int count=13;
//        int[] result=insertionSort(list,count);
        insertionSort(list);
//        System.out.println("排序后： "+ Arrays.toString(result));
        System.out.println("排序后： "+ Arrays.toString(list));
    }

    private static int[] insertionSort(int[] list, int count) {
        int[] result= Arrays.copyOf(list, list.length);

        for (int i = 1; i < list.length; i++) {

            int j=i;
            while (j > 0 && list[i]<result[j-1]) {
                result[j]=result[j-1];
                j--;
            }
            result[j]=list[i];
        }

        return  result;
    }


    public static void insertionSort(int[] arr){
        for(int i=1;i<arr.length;i++){
            int j=i;
            while(j>0 && arr[j] < arr[j - 1]){
                arr[j] = arr[j]+arr[j-1];
                arr[j-1] = arr[j]-arr[j-1];
                arr[j] = arr[j]-arr[j-1];
                j--;
            }
        }
    }

}
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

选择排序

我觉得选择排序最符合人的排序习惯，就是一轮一轮的找最小的，拿出来排队。

/**
 * 选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
 */
public class SelectionSort {

    public static void main(String[] args) {
        int[] list= {81,94,11,96,12,35,17,95,28,58,41,75,15};
        System.out.println("排序前： "+ Arrays.toString(list));

        int count=13;
        selectSort(list);
        System.out.println("排序后： "+ Arrays.toString(list));
    }

    private static void selectioonSort(int[] list, int count) {
        for (int i = 0; i < list.length-1; i++) {
            int min=i;
            for (int j = i + 1; j < list.length; j++) {
                if(list[min]>list[j]){
                    min=j;
                }
            }

            if (min!=i){
                int temp=list[i];
                list[i]=list[min];
                list[min]=temp;
            }

        }
    }

    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length-1; i++) {
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }

            if (min != i) {
                arr[min]=arr[min]+arr[i];
                arr[i]=arr[min]-arr[i];
                arr[min]=arr[min]-arr[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
51
52

希尔排序

希尔排序按其设计者希尔（Donald Shell）的名字命名，该算法由1959年公布。一些老版本教科书和参考手册把该算法命名为Shell-Metzner，即包含Marlene Metzner Norton的名字，但是根据Metzner本人的说法，“我没有为这种算法做任何事，我的名字不应该出现在算法的名字中。

希尔排序可以理解为在插入排序外面套了一层，每次不是相近的数字在比，而是间隔着比，主要是为了提高消灭逆序对的效率

/**
 * 希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
 * 希尔排序是基于插入排序的以下两点性质而提出改进方法的：
 * 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
 * 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
 * 希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] list= {81,94,11,96,12,35,17,95,28,58,41,75,15};
        System.out.println("排序前： "+ Arrays.toString(list));

        int count=13;
        shellSort2(list,count);
        System.out.println("排序后： "+ Arrays.toString(list));
    }


    private static void shellSort(int[] list, int count) {
        for (int D = count/2; D >0 ; D/=2) {
            for (int P = D; P < count; P++) {
                int temp=list[P];
                int i;
                for (i = P; i >= D && list[i-D] > temp; i-=D) {
                    list[i]=list[i-D];
                }
                list[i]=temp;

            }
        }
    }

    private static void shellSort2(int[] arr, int count) {
        for (int D = count/2; D >0 ; D/=2) {
            for(int i=D;i<arr.length;i++){
                int j=i;
                while(j>=D && arr[j] < arr[j - D]){
                    arr[j] = arr[j]+arr[j-D];
                    arr[j-D] = arr[j]-arr[j-D];
                    arr[j] = arr[j]-arr[j-D];
                    j-=D;
                }
            }
        }
    }
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

归并排序

归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为
$O(nlogn)$（大O符号）。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

我觉得靠我的脑子想不出来归并排序这种东西，就是拆分到最小单位，1个或者两个，然后排好序返回来，有序的列表继续参与合并排序。

/**
 * 归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
 * 作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
 * 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
 * 自下而上的迭代；
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] list= {81,94,11,96,12,35,17,95,28,58,41,75,15};
        System.out.println("排序前： "+ Arrays.toString(list));

        int count=13;
        int[] result=sort(list);
        System.out.println("排序后： "+ Arrays.toString(result));
    }


    private static int[] sort(int[] list){
        int middle = (int) Math.floor(list.length / 2);

        if(list.length<2){
            return list;
        }
        int[] left=Arrays.copyOfRange(list,0,middle);
        int[] right=Arrays.copyOfRange(list,middle,list.length);

        return merge(sort(left),sort(right));
    }

    private static int[] merge(int[] left, int[] right) {
        int[] result=new int[left.length+right.length];
        int i=0;
        while (left.length>0 && right.length>0){
            if (left[0]> right[0]){
                result[i]=right[0];
                right=Arrays.copyOfRange(right,1,right.length);
            }else {
                result[i]=left[0];
                left=Arrays.copyOfRange(left,1,left.length);
            }
            i++;
        }

        while (left.length>0){
            result[i++]=left[0];
            left=Arrays.copyOfRange(left,1,left.length);
        }

        while (right.length>0){
            result[i++]=right[0];
            right=Arrays.copyOfRange(right,1,right.length);
        }
        return result;
    }
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

快速排序

由英国计算机科学家托尼·霍尔（Tony Hoare）于1959年想到的，1961年发表的，这个算法也成了今天世界计算机产业中使用最多的排序算法，霍尔因此获得了爵士头衔，也成为第一个获得这种头衔的科学家。

/**
 * 快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想----分治法也确实实用
 * 快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
 * 该方法的基本思想是：
 * 1．先从数列中取出一个数作为基准数。
 * 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
 * 3．再对左右区间重复第二步，直到各区间只有一个数。
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] list= {81,94,11,96,12,35,17,95,28,58,41,75,15};
        System.out.println("排序前： "+ Arrays.toString(list));

        int count=13;
        quickSort(list,0,count-1);
        System.out.println("排序后： "+ Arrays.toString(list));
    }

    private static void quickSort(int[] list, int low,int high) {

        if(low>=high){
            return;
        }
        int piovt=list[low];

        int left=low;
        int right=high;
        while (left<right){
            while (left<right&&list[right]>=piovt){
                right--;
            }
            if (left<right){
                list[left]=list[right];
            }
            while (left<right&&list[left]<piovt){
                left++;
            }
            if (left<right){
                list[right]=list[left];
            }
            if (left>=right){
                list[left]=piovt;
            }
        }

        quickSort(list,low,right-1);
        quickSort(list,right+1,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
43
44
45
46
47
48
49
50
51

堆排序

计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W．Floyd）和威廉姆斯(J．Williams）在1964年共同发明了堆排序算法。

堆排序Heapsort 是J. W. J. Williams在1964年发明的。这也是堆诞生的时候，Williams 将其本身作为一个有用的数据结构提出。同年，R. W. Floyd发表了一个改进的版本，可以对数组进行就地排序，继续他早期对treesort 算法的研究。

/**
 * 堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
 * 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
 * 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
 * 堆排序的平均时间复杂度为 Ο(nlogn)。
 */
public class Heapsort {

    public static void main(String[] args) {
        int[] list= {81,94,11,96,12,35,17,95,28,58,41,75,15};
        System.out.println("排序前： "+ Arrays.toString(list));

        int count=13;
        heapSort(list,count);
        System.out.println("排序后： "+ Arrays.toString(list));
    }

    private static void heapSort(int[] list, int count) {

        for (int k = count-1; k > 1; k--) {
            for (int i = 0; i <=k; i++) {
                int left=2*i+1;
                int right=2*i+2;
                if(left<k && list[left]<list[i]){
                    int temp=list[i];
                    list[i]=list[left];
                    list[left]=temp;
                }
                if(right<k && list[right]<list[i]){
                    int temp=list[i];
                    list[i]=list[right];
                    list[right]=temp;
                }

                if (right<k && list[right]<list[left]){
                    int temp=list[left];
                    list[left]=list[right];
                    list[right]=temp;
                }

            }
            int min=list[0];
            list[0]=list[k];
            list[k]=min;
        }

    }

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

基数排序

基数排序（英语：Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到1887年赫尔曼·何乐礼在列表机（Tabulation Machine）上的贡献。

这个真的写起来好麻烦，照着菜鸟教程写的，改了六七遍才跑通。

/**
 * 基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] list= {81,94,11,96,12,35,17,95,28,58,41,75,15};
        System.out.println("排序前： "+ Arrays.toString(list));

        int count=13;
        radixSort(list,count);
        System.out.println("排序后： "+ Arrays.toString(list));
    }

    private static void radixSort(int[] list, int count) {
//        int[] result=Arrays.copyOf(list,list.length);

        LinkedList<Integer>[] linkedLists = new LinkedList[10];
        for (int i = 0; i < linkedLists.length; i++) {
            linkedLists[i] = new LinkedList<>();
        }
        int max=getMax(list);
        for (int i = 1; i <=max; i++) {
            for (int j = 0; j < list.length; j++) {
                linkedLists[getIndex(list[j],i)].offer(list[j]);
            }

            int index=0;

            for (int j = 0; j < linkedLists.length; j++) {
                while (!linkedLists[j].isEmpty()){
                    list[index++]=linkedLists[j].poll();

                }
            }
        }

//        return result;
    }

    private static int getMax(int[] list) {
        int max=list[0];
        for (int i = 0; i < list.length; i++) {
            if (list[i]>max){
                max=list[i];
            }

        }
        return (max + "").length();
    }


    private static int getIndex(int num, int r) {
        int ret = 0;
        for (int i = 1; i <= r; i++) {
            ret = num % 10;
            num /= 10;
        }
        return ret;
    }

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
59
60
61