四种常见的排序算法

1.冒泡排序

思想: 每一趟将待排序序列中最大元素移到最后，剩下的为新的待排序序列, 重复上述步骤直到排完所有元素。这只是冒泡排序的一种, 当然也可以从后往前排

平均时间复杂度: O(n^2)

public class Demo {
    public void bubbleSort(int arr[]) {
        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 temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr={4, 8, 7, 5, 6, 3, 1};
        Demo d = new Demo();
        d.selectSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

2.选择排序

思想: 每一趟从待排序序列选择一个最小的元素放在已排好序列的末尾, 剩下的为待排序序列, 重复上述步骤直至完成排序

平均时间复杂度: O(n^2)

public void selectSort(int arr[]) {
    //选择
    for (int i = 0; i < arr.length; i++) {
        //默认第一个是最小的。
        int min = arr[i];
        //记录最小的下标
        int index = i;
        //通过与后面的数据进行比较得出，最小值和下标
        for (int j = i + 1; j < arr.length; j++) {
            if (min > arr[j]) {
                min = arr[j];
                index = j;
            }
        }
        //然后将最小值与本次循环的，开始值交换
        int temp = arr[i];
        arr[i] = min;
        arr[index] = temp;
        //说明：将i前面的数据看成一个排好的队列，i后面的看成一个无序队列。每次只需要找无需的最小值，做替换
    }
}

3.插入排序

思想: 1. 默认从第二个数据开始比较。

　　 2.如果第二个数据比第一个小，则交换。然后在用第三个数据比较，如果比前面小，则插入（狡猾）。否则，退出循环

　　 3.说明：默认将第一数据看成有序列表，后面无序的列表循环每一个数据，如果比前面的数据小则插入（交换）。否则退出

平均时间复杂度: O(n^2)

public void insertSort(int arr[]) {
    //插入排序
    for (int i = 1; i < arr.length; i++) {
        //外层循环，从第二个开始比较
        for (int j = i; j > 0; j--) {
            //内存循环，与前面排好序的数据比较，如果后面的数据小于前面的则交换
            if (arr[j] < arr[j - 1]) {
                int temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
            } else {
                //如果不小于，说明插入完毕，退出内层循环
                break;
            }
        }
    }
}

4.快速排序

采用分治法的思想：首先设置一个轴值pivot，然后以这个轴值为划分基准将待排序序列分成比pivot大和比pivot小的两部分，接下来对划分完的子序列进行快排直到子序列为一个元素为止。

平均时间复杂度: O(n*log(n))

public class Demo {    
	public void quickSort(int arr[], int low, int high) {
        //pivot:位索引;p_pos:轴值
        int pivot, p_pos, i, temp;
        if (low < high) {
            p_pos = low;
            pivot = arr[p_pos];
            for (i = low + 1; i <= high; i++) {
                if (arr[i] > pivot) {
                    p_pos++;
                    temp = arr[p_pos];
                    arr[p_pos] = arr[i];
                    arr[i] = temp;
                }
            }
            temp = arr[low];
            arr[low] = arr[p_pos];
            arr[p_pos] = temp;
            //分而治之
            quickSort(arr, low, p_pos - 1);//排序左半部分
            quickSort(arr, p_pos + 1, high);//排序右半部分
        }
    }
	public static void main(String[] args) {
        int[] arr = {4, 8, 7, 5, 6, 3, 1};
        Demo d = new Demo();
 	    d.quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

注: 各排序时间复杂度

排序方法 平均情况 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定
选择排序 O(n^2) O(n^2) O(n^2) O(1) 不稳定
插入排序 O(n^2) O(n) O(n^2) O(1) 稳定
希尔排序O(n*log(n))~O(n^2) O(n^1.3) O(n^2) O(1) 不稳定
堆排序 O(nlog(n)) O(nlog(n)) O(n*log(n)) O(1) 不稳定
归并排序 O(nlog(n)) O(nlog(n)) O(n*log(n)) O(n) 稳定
快速排序 O(nlog(n)) O(nlog(n)) O(n^2) O(1) 不稳定