2017-06-28-常见的排序算法总结

• 1，冒泡排序
• 2，简单选择排序
• 3，直接插入排序
• 4，快速排序
• 5，归并排序
• 6，堆排序
• 7，希尔排序(最小增量排序)
• 8，基数排序

1,简单选择排序

• 在要排序的一组数中，选出最小的一个数与第一个位置的数交换；
• 然后在剩下的数当中再找最小的与第二个位置的数交换，
• 如此循环到倒数第二个数和最后一个数比较为止
• 时间复杂度是n的平方

代码实现

 private static void simple(int[] arr) {
    final int len = arr == null ? 0 : arr.length;
    int position;
    for (int i = 0; i < len; i++) {
        position = i;
        int temp = arr[i];
        for (int j = i + 1; j < len; j++) {
            if(arr[j] < temp) {
                temp = arr[j];
                position = j;
            }
        }
        arr[position] = arr[i];
        arr[i] = temp;
    }
}

2，冒泡排序

• 时间复杂度是O(n)
• 空间复杂度是s(1)
• 基本思想：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，
• 让较大的数往下沉，较小的往上冒。
• 即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

代码实现

@Override
public void sort(int[] arr) {
    final int len = arr == null ? 0 : arr.length;
    for (int i= 0; i < len - 1; i++) {
        for (int j = i + 1; j < len; j++) {
            int temp;
            if(arr[i] > arr[j]) {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

3，快速排序

• 利用的是二分查找的思想
• 基本思想：选择一个基准元素，通常是第一个或者最后一个，通过一趟扫描，将待排序的元素分为俩部分，
• 一部分小于基准元素，一部分大于等于比基准元素
• 此时基准元素位于其排好序的正确的位置
• 然后再用同样的方法递归

代码实现如下

@Override
public void sort(int[] arr) {
    if(arr == null)arr = this.arr;
    final int len = arr.length;
    quickSort(arr, 0 , len - 1);
    printArr(arr);
}


private void quickSort(int[] arr, int low, int high) {
    if(low < high) {
        int middle = getMiddle(arr, low, high);
        quickSort(arr, low, middle - 1);
        quickSort(arr, middle + 1, high);
    }
}

private int getMiddle(int[] arr, int low, int high) {
    int middle = 0;
    int temp = arr[low];//数组的第一个作为中轴
    while (low < high) {
        while (low < high && arr[high] >= temp) {
            high--;
        }
        arr[low] = arr[high];// //比中轴小的记录移到低端
        while (low < high && arr[low] <= temp) {
            low ++;
        }
        arr[high] = arr[low];//比中轴大的记录移到高端
    }
    arr[low] = temp;
    middle = low;//返回中轴的位置
    return middle;
}

4，直接插入排序

• 基本思想：在要排序的一组数中，假设前面(n-1)[n>=2] 个数已经是排
• 好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数
• 也是排好顺序的。如此反复循环，直到全部排好顺序。
• 时间复杂度o(n*n) 空间复杂度s(1)

    @Override
    public void sort(int[] arr) {
        if (arr == null) arr = this.arr;
        final int len = arr.length;
        int temp = 0;
        for (int i = 1; i < len; i++) {
            int j = i -1;
            temp = arr[i];
            while (j >= 0 && temp < arr[j]) {//将大于temp的值整体后移一个单位
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;
        }
        printArr(arr);
    }