各类排序算法总结（持续更新中）

2019-08-25 本文已影响0人居居居居居居x

先来一张各类排序的时间复杂度的总结表

此图来源网络

1.选择排序（SelctionSort）

import java.util.Scanner;

public class SelectionSort {


    public void sort() {
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        int[] array = new int[size];
        for (int i = 0; i < size; i++) {
            array[i] = sc.nextInt();
        }

        //开始选择排序
        for (int i =0;i<size;i++){
            int minindex = i; //选择第一个为默认min
            //遍历i+1~size后面的值，如果比它小，就赋值，以此内推
            for (int  j = i+1;j<size;j++){
                if (array[j] <array[minindex]){
                    minindex = j;
                }
            }
            
            //然后进行交换
            int temp = array[minindex];
            array[minindex] = array[i];
            array[i] = temp;
        }

        for (int sum : array){
            System.out.println(sum);
        }
    }
}

选择排序结果

思路

来自网路，侵删

思路很简单，我们首先遍历找出最小的值，然后记住它的坐标，然后通过坐标在和现在的第i个坐标进行交换值，以此类推，排序就完成了。它的时间复杂度是O（n2）。

2.插入排序（Insertion Sort）

版本一

import java.util.Scanner;

public class InsertionSort {

    public void sort() {
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = sc.nextInt();
        }


        //开始插入排序
        for (int i = 1; i < size; i++) {

            //寻找元素arr[i]合适的插入位置
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    //进行交换
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
            }
        }

        for (int sum : arr){
            System.out.println(sum);
        }
    }

}

思路

来自网络，侵删

首先对于第一个元素不不动，从第二个元素开始跟前面相比，如果比它小就进行交换，随后回到交换后的位置，再次跟他前面的数相比较，以此类推，完成排序。
但是这样子有一个缺点，因为每次遍历的时候都要交换，交换是很消耗时间，故此进行优化。

版本二

 public void sortTwo() {
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = sc.nextInt();
        }

        //开始插入排序
        for (int i = 1; i < size; i++) {
            int e = arr[i];
            int j; //保存的是元素要插入的位置
            //寻找元素arr[i]合适的插入位置
            for (j = i; j > 0; j--) {
                if (arr[j - 1] > e) {
                    arr[j] = arr[j - 1];
                } else {
                    break;
                }
            }
            arr[j] = e;
        }

        for (int sum : arr) {
            System.out.println(sum);
        }
    }

先把要插入的元素的位置复制一份出来，然后跟前面的位置进行比较，如果前面的位置比要插入的元素要大的话，就复制一份给要判断的位置，直到无法判断，这是位置j就是该元素要插入的位置，就直接进行赋值就好啦。

3.冒泡排序（Bubble Sort）

public static void sort() {
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        int[] array = new int[size];
        for (int i = 0; i < size; i++) {
            array[i] = sc.nextInt();
        }

        int len = array.length;
        //开始冒泡排序，从小到大
        for (int i = 0; i < len - 1; i++) {
            for (int j = 0; j < len - i - 1; j++) {
                if (array[j + 1] < array[j]) {
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
            }
        }

        for (int num : array) {
            System.out.println(num);
        }

    }

冒泡排序过程，侵删

时间复杂度为O(N2)，是一个比较稳定的算法。

4.希尔排序（Shell Sort）

public class ShellSort {

    public void sort(int[] sums, int lenth) {


        for (int step = lenth; step > 0; step = step / 2) {


            for (int i = step; i < lenth; i++) {

                int j = i;
                int temp = sums[j];

                while (j - step >= 0 && sums[j - step] > temp) {
                    sums[j] = sums[j - step];
                    j = j - step;
                }
                sums[j] = temp;
            }
        }
    }
}

希尔排序算是插入排序的改进版，具体流程内容参考希尔排序就怎么简单。

5.快速排序（Quick Sort）

public static void quickSort(int[] array, int l, int r) {
    if (l >= r) {
        return;
    }

    int i = l;
    int j = r;
    //选择数组的第一个数作为中点来判断
    int key = array[l];

    while (i < j) {

        //从右边开始找第一个小于key的值
        while (i < j && array[j] >= key) {
            j--;
        }
        if (i < j) {
            array[i] = array[j];
            i++;
        }

        //从左边开始找第一个大于key的值
        while (i < j && array[i] < key) {
            i++;
        }
        if (j < j) {
            array[j] = array[i];
            j--;
        }
    }

    array[i] = key;
    quickSort(array, l, i - 1);
    quickSort(array, i + 1, r);
}

快速排序主要运用了分治法的思想，选定一个数为中数（一般默认数组的第一个数），然后进行排序，比中数小的都移在左边，比中数大的，都移在右边，然后再把中数左右两边的数组通过递归形式再次跟刚才的思想进行调用，最后变成一个数的时候，排序就完成了。

6.归并排序

public class MergeSort {


    public static void mergeSrot(int[] array, int n) {
        //后面两个分别为开始位置和结束位置[l,r]
        merge(array, 0, n - 1);
    }
    
    private static void merge(int[] array, int l, int r) {

        if (l >= r) {
            return;
        }

        int mid = (l + r) / 2;

        merge(array, l, mid);
        merge(array, mid + 1, r);
        //进行归并合并，这里是有一个优化点，
        if (array[mid] > array[mid + 1]) {
            merge(array, l, mid, r);
        }
    }

    private static void merge(int[] array, int l, int mid, int r) {

        int[] aux = new int[r - l + 1];
        for (int i = l; i <= r; i++) {
            aux[i - l] = array[i];
        }

        int i = l;
        int j = mid + 1;
        for (int k = l; k <= r; k++) {

            if (i > mid) {
                array[k] = aux[j - l];
                j++;
            } else if (j > r) {
                array[k] = aux[i - l];
                i++;
            } else if (aux[i - l] < aux[j - l]) {
                array[k] = aux[i - l];
                i++;
            } else {
                array[k] = aux[j - l];
                j++;
            }
        }
    }
}