排序

0.复杂度

0.1 时间复杂度

语句执行的次数 数量级

0.2 空间复杂度

1.交换排序

1.1冒泡排序

/**
* 两层循环，相邻比较交换
*/
for (int i = 0; i < arr.length - 1; i++) {
    for (int j = 0; j < arr.length - 1 - i; j++) {
        if (arr[j] > arr[j + 1]) {
            int t = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = t;
        }
    }
}

1.2 快速排序

public class QuickSort {
    /**
     * 快速排序：
     */
    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            //中间值
            int pivot = arr[left];
            int l = left, r = right;
            //从左往右，将比pivot大的放右边
            while (l < r) {
                //在pivot右边找到比pivot小的一个
                while (l < r && pivot <= arr[r]) {
                    r--;
                }
                arr[l] = arr[r];
                //在pivot左边找到比pivot大的一个
                while (l < r && arr[l] <= pivot) {
                    l++;
                }
                arr[r] = arr[l];
            }
            arr[l] = pivot;//重合位
            quickSort(arr, left, l);
            quickSort(arr, l + 1, right);
        }
    }   
    public static void main(String[] args) {
        int[] a = {2, 5, 3, 10, 2, 9, 8, 6, 7};
        quickSort(a,0,a.length-1);
        System.out.println(Arrays.toString(a));
    }
}

2.插入排序

2.1 直接插入

/**
* 将无序部分的首位依次与有序部分依次比较，同时交换位置，直到到达合适位置
*/
for (int i = 1; i < arr.length; i++) {    
    int num = arr[i];//记录要插入的数
    int j;//标记移动位置
    for (j = i - 1; j >= 0; j--) {
        if (num < arr[j]) {
            arr[j + 1] = arr[j];//原位置直接覆盖
        } else {
            break;
        }
    }
    arr[j + 1] = num;//arr[j]放在最后空出的位置
}

2.2 希尔排序

public class ShellSort {
    /**
     * 希尔排序：依次跳跃式分组排序
     */
    public static void shellSort1(int[] arr) {
        //第一轮排序，gap为总长一半
        int temp = 0;
        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]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
        }
    }
    public static void shellSort2(int[] arr) {
        /**
         * 移位式
         */
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            //从第gap个开始，组内进行插入排序
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                //将 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;
                }
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 4, 5, 0};
        shellSort2(arr);
        System.out.println(Arrays.toString(arr));
    }
}

3.选择排序

3.1 简单选择

for (int i = 0; i < arr.length; i++) {
    int min = i;
    for (int j = i; j < arr.length; j++) {
        if (arr[j] < arr[min]) {
            min = j;
        }
    }
    int temp = arr[i];
    arr[i] = arr[min];
    arr[min] = temp;
}

3.2 堆排序

4.其他排序

4.1 归并排序

public class MergeSort {
    /**
     * 归并排序
     */
    public static void merge(int[] arr, int low, int mid, int high) {
        //临时数组
        int[] temp = new int[high - low + 1];
        int index = 0;
        //记录两段的下标
        int i = low, j = mid + 1;
        while (i <= mid && j <= high) {
            //将两段合并排序存入temp
            if (arr[i] <= arr[j]) {
                temp[index++] = arr[i++];
            } else {
                temp[index++] = arr[j++];
            }
        }
        //可能有剩余
        while (j <= high) {
            temp[index++] = arr[j++];
        }
        while (i <= mid) {
            temp[index++] = arr[i++];
        }
?
        for (int k = 0; k < temp.length; k++) {
            arr[k + low] = temp[k];
        }
    }
    //排序入口
    public static void mergeSort(int[] arr, int low, int high) {
        int mid = (low + high) / 2;
        //递归返回
        if (low >= high) return;
        mergeSort(arr, low, mid);
        mergeSort(arr, mid + 1, high);
        merge(arr, low, mid, high);
    }
?
    public static void main(String[] args) {
        int[] arr = new int[10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int)(Math.random()*100);
        }
        mergeSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
}

4.2 基数排序

public class RadixSort {
    public static void radixSort(int[] arr) {
        //找到最大元素
        int max = Integer.MIN_VALUE;
        for (int i : arr) {
            if (i > max) {
                max = i;
            }
        }
        //临时存放
        int maxLength = (max + "").length();
        int[][] temp = new int[10][arr.length];
        int[] counts = new int[10];
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            for (int j = 0; j < arr.length; j++) {
                //根据第i位数字进行分组
                int ys = arr[j] / n % 10;
                temp[ys][counts[ys]] = arr[j];
                counts[ys]++;
            }
            //将排序后的放回原数组
            int index = 0;
            for (int j = 0; j < counts.length; j++) {
                if (counts[j] != 0) {
                    for (int k = 0; k < counts[j]; k++) {
                        arr[index++] = temp[j][k];
                    }
                    counts[j] = 0;//重置分组
                }
            }
        }
    }
?
    public static void main(String[] args) {
        int[] arr = {123,33,66,45,186,3135,22,335,666,159,987};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

5.排序算法总结

5.1 复杂度

排序算法

原文：https://www.cnblogs.com/fremontxutheultimate/p/14616837.html