排序算法 —— 插入排序、选择排序、冒泡排序、快速排序

欢迎指正。

最近打算重温一下排序算法。

插入排序

原理

插入排序主要是通过构建有序序列，对未排列的数据，从后往前扫描，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。

代码

public static void InsertSort(int[] array) {

    for (int i = 1; i < array.length; i++) {
        int j = i;
        int target = array[i];
        while (j > 0 && target < array[j - 1]) {
            array[j] = array[j - 1];
            j--;
        }
        array[j] = target;
    }
}

选择排序

原理

第一次从下标为0的开始下标为0的这个数与后面的n-1个进行比较；找出最小或者最大的放在下标为0的这个位置。

时间复杂度是O(n^2)。不稳定

代码

public static void SelectionSort(int[] array) {

    for (int i = 0; i < array.length; i++) {

        for (int j = i + 1; j < array.length; j++) {
            if (array[i] > array[j]) {
                int target = array[i];
                array[i] = array[j];
                array[j] = target;
            }
        }
    }
}

冒泡排序

原理

• 从第一个数据开始，与第二个数据相比较，如果第二个数据小于第一个数据，则交换两个数据的位置。
• 指针由第一个数据移向第二个数据，第二个数据与第三个数据相比较，如果第三个数据小于第二个数据，则交换两个数据的位置。
• 依此类推，完成第一轮排序。第一轮排序结束后，最大的元素被移到了最右面。
• 依照上面的过程进行第二轮排序，将第二大的排在倒数第二的位置。
• 重复上述过程，没排完一轮，比较次数就减少一次。

代码

public static void BubbleSort(int[] arr){
    int i, j;
    int n = arr.length;
    int target;
    for (i = 0; i < n - 1; i++) {

        for (j = 0; j < n - 1 - i; j++) {
            //左边比右边大
            if (arr[j] > arr[j + 1]) {
                target = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = target;
            }
        }
    }
}

快速排序

原理

快排的原理：在需要排序的数据中选择一个中心值（key）,通过一趟排序将需要排序的数组分为两部分，其中以key为中心，key右边比key大，key左边比key小，然后重复这过程。

代码

public static void quickSort(int a[]) {
    sort(a, 0, a.length - 1);
}

public static void sort(int a[], int low, int hight) {
    int i, j, target;
    if (low > hight) {
        return;
    }
    i = low;
    j = hight;
    target = a[i];
    while (i < j) {
        while (i < j && a[j] >= target) {
            j--;
        }
        // 用比基准小的记录替换低位记录
        if (i < j) {
            a[i++] = a[j];
        }
        while (i < j && a[i] < target) {
            i++;
        }
        // 用比基准大的记录替换高位记录
        if (i < j) {
            a[j--] = a[i];
        }
    }
    // 将基准数值替换回 a[i]
    a[i] = target;
    // 对低子表进行递归排序
    sort(a, low, i - 1);
    // 对高子表进行递归排序
    sort(a, i + 1, hight);
}