排序算法总结 java-蒲公英云

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	是否稳定
冒泡排序	O(n²)	O(n)	O(n²)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
插入排序	O(n²)	O(n)	O(n²)	O(1)	稳定
希尔排序	O(nlogn)	O(nlog²n)	O(nlog²n)	O(1)	不稳定
归并排序	O(nlogn)	O(nlogn)	O(n^s)	O(n)	稳定
快速排序	O(nlogn)	O(nlogn)	O(n²)	O(logn)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定
基数排序	O(nk)	O(nk)	O(n*k)	O(n+k)	稳定
桶排序	O(n+k)	O(n+k)	O(n²)	O(n+k)	稳定

冒泡排序

比较相邻两个元素，如果no.2 < no.1，就交换两个元素。
对每一对相邻元素进行一样的操作，从第一对一直到结尾的最后一对。

针对所有元素重复上述步骤，除了最后一个。

public class MaoPao {

public static void main(String[] args) {
    int[] arr = new int[]{
3,9,-1,10,2};
    bubblesort(arr);
    System.out.println(Arrays,toString(arr));
}
public static int[] bubblesort(int[] arr) {
    if (arr == null || arr.length < 2) return arr;
    int n = arr.length;
    for (int i = 0; i < n; i++) {
        boolean flag = true;
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                flag = false;
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
        //flag = true证明数组已经是按顺序排序了，一次交换也没有，可以直接退出循环。
        if (flag) {
            break;
            }
    }
    return arr;
}

}

选择排序

在数组中找到最小的元素，将它与第一个元素进行交换

在剩下的元素中找到最小的元素，与第二个元素交换

public class SelectSort {

public static void main(String[] args) {
    int[] arr = new int[]{
3,0,-9,1,2};
    selectsort(arr);
    System.out.println(Arrays.toString(arr));
}
public static int[] selectsort(int[] arr) {
    int n = arr.length;
    for (int i = 0;i < n-1;i++) {
        //假设第一个元素是最小的。
        int min = i;
        for (int j =i+1; j < n; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        //证明第一个元素不是最小的，交换
        if (i != min) {
            int temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
    }
    return arr;
}

}

插入排序

将数组看作一个有序表和一个无序表，开始的时候，有序表中只有一个元素，无序表是除了第一个元素剩下的所有元素。

排序过程中，每次从无序表中抽出第一个元素，与有序表进行比较，插入到合适的位置。

public class InsertSort {

public static void mian(String[] args) {
    insertsort(arr);
    System.out.println(Arrays.toString(arr));
}
public static int[] insertsort(int[] arr) {
    for (int i = 1; i < arr.length;i++) {
        int temp = arr[i];
        int j = i-1;
        while (j >= 0 && temp < arr[j]) {
            //有序表扩大，大的元素放在后面
            arr[j+1] = arr[j];
            // 向前移，比较有序表之前的元素和当前元素的大小
            j--;
        }
        //此时j=-1，
        //或者temp>arr[j] 
        arr[j+1] = temp;
    }
    return arr;
}

}

希尔排序

public class ShellSort {
    public static void main(String[] args) {
        int[] arr= new int[]{
    8,9,1,7,2,4,5,3,6,0};
        shellsort(arr);//交换
        shellmove(arr);
        System.out.println(Arrays.toString(arr));
    }
    //这是希尔排序的交换法
    public static int[] shellsortexchange(int[] arr) {
        for (int gap = arr.length/2 ;gap > 0; gap /=2) {
            for (int i = gap; i < arr.length; i++) {
                for (int j = i-gap; j >= 0;j -= gap) {
                    if (arr[j] > arr[j+gap]) {
                        int temp = arr[j];
                        arr[j] = arr[j+gap];
                        arr[j+gap] = temp;                    
                    }
                }
            }
        }
        return arr;
    }
    public static int[] shellsortmove(int[] arr) {
        for (int gap = arr.length/2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                if(arr[j] < arr[j-gap]) {
                    while (j-gap >= 0 && temp < arr[j-gap]) {
                        //移动
                        arr[j] = arr[j-gap];
                        j -= gap;
                    }
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }
}

归并排序

归并排序是用归并的思想实现的排序方法，该算法采用经典的分治策略，分：将问题分为小的问题递归求解；治：将分的阶段得到的答案修补。
在这里插入图片描述

public static int[] mergosort(int[] arr,int left,int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        arr = mergosort(arr,left,mid);
        arr = mergosort(arr,mid+1,right);
        mergo(arr,left,mid,right);
    }
    return arr;
}
public static void mergo(int[] arr,int left, int mid,int right) {
    int[] str = new int[right-left+1];
    int l = left;
    int j = mid+1;
    int k = 0;
    while (l < j && j <= right){
        if (arr[l]< arr[j]) {
            str[k] = arr[l];
            k++;
            l++;
        }else {
            str[k] = arr[j];
            k++;
            j++;
        }            
    }
    while (l <= mid) {
        str[k] = arr[l];
        k++;
        l++;
    }
    while (j <= right) {
        str[k] = arr[j];
        k++;
        j++;
    }
    for (int i = 0;j <k;i++){
        arr[left] = str[i];
        left++;
    }
    }
}

快速排序

快速排序：

选定pivot中心轴（这里的pivot一开始选择是数组第一个元素）
将大于pivot的数字放在pivot的右边
将小于pivot的数字放在pivot的左边

分别左右子序重复前三步操作

public static void main(String[] args) {

int[] arr = {
-9,78,0,23,-567,70};
quicksort(arr,0,arr.length-1);

}
public static void quicksort(int[] arr, int left,int right){

if (left > right) return;
int l = left;
int r = right;
int pivot = arr[l];
while (l < r) {
    while (l < r && arr[r] >= pivot){
        r--;
    }
    if (l < r) {
        arr[l] = arr[r];
    }
    while (l < r && arr[l] <= pivot){
        l++;
    }
    if (l < r){
        arr[r] = arr[l];
    }
    if (l >= r){
        arr[l] = pivot;    
    }
}
quicksort(arr,left,r-1);
quicksort(arr,r+1,right);