七大经典排序算法：原理、实现与复杂度分析

1
public static void quickSort(int[] array) {
2
    quick(array,0,array.length - 1);
3
}
4

5
void quick(int[] array, int left, int right) {
6
    // 递归终止条件：区间内没有元素或只有一个元素
7
    if (left >= right) {
8
        return;
9
    }
10
    // 分区操作：将数组分成两部分，并返回基准元素的最终位置
11
    int pivot = partition(array, left, right);
12
    // 递归排序左半部分：[left, pivot]
13
    quick(array, left, pivot);
14

15
    // 递归排序右半部分：[pivot+1, right]
16
    quick(array, pivot + 1, right);
17
}

1
    private static int partition (int[] array, int left, int right) {
2
        int tmp = array[left];
3
        int tmpLeft = left;
4
        // 双指针在数组中移动判断
5
        while (right > left) {
6
            while (right > left && array[right] >= tmp)
7
                right--;
8
            while (left < right && array[left] <= tmp)
9
                left++;
10
            swap(array,right,left);
11
        }
12
        // 走完循环后，基准值还需与中间值交换
13
        swap(array,left,tmpLeft);
14
        return left;
15
    }

1
    private static int hole_Partition (int[] array, int left, int right) {
2
        int tmp = array[left];
3
        // 循环条件
4
        while (left < right) {
5
            while (left < right && array[right] >= tmp)
6
                right--;
7
            // 若右指针跳出循环停下，则右侧赋给左侧
8
            array[left] = array[right];
9

10
            while(left < right && array[left] <= tmp)
11
                left++;
12
            // 若左指针跳出循环停下，则左侧赋给右侧
13
            array[right] = array[left];
14
        }
15
        // 最终相遇，将tmp拿回放中间
16
        array[left] = tmp;
17
        return left;
18
    }

1
    // 双指针法
2
    private static int twop_Partition (int[] array, int left, int right) {
3
        // 暂存基准值
4
        int tmp = array[left];
5
        int prev = left;
6
        int cur = prev + 1;
7

8
        while (cur <= right) {
9
            // a. 若 array[cur] < tmp，说明找到比基准小的值
10
            if (array[cur] < tmp) {
11
                // b. prev++，扩大小于基准的区域
12
                prev++;
13
                // c. 若 array[prev] != array[cur]，则交换
14
                if (array[prev] != array[cur])
15
                    swap(array,prev,cur);
16
            }
17
            cur++;
18
        }
19
        // 最后将基准值填入 prev 位置
20
        swap(array,left,prev);
21
        return prev;
22
    }

1
void quickSort(int[] array, int left, int right) {
2
    // 递归终止条件：区间内没有元素或只有一个元素
3
    if (left >= right) {
4
        return;
5
    }
6
    // 三数取中法调用出
7
    getMiddle(array,)
8

9
    // 分区操作：将数组分成两部分，并返回基准元素的最终位置
10
    int pivot = partition(array, left, right);
11
    // 递归排序左半部分：[left, pivot]
12
    quickSort(array, left, pivot);
13

14
    // 递归排序右半部分：[pivot+1, right]
15
    quickSort(array, pivot + 1, right);
16
}

1
private static int getMiddle (int[] array, int left, int right) {
2
    // 找到中位置
3
    int mid = (left + right) / 2;
4

5
    if (array[left] < array[right]) {
6
        if (array[mid] < array[left])
7
            return left;
8
        else if (array[mid] > array[right])
9
            return right;
10
        else
11
            return mid;
12
    } else {
13
        if (array[mid] < array[right])
14
            return right;
15
        else if(array[mid] > array[left])
16
            return left;
17
        else
18
            return mid;
19
    }
20
}

1
private static void quick(int[] array,int start,int end) {
2
    if (start >= end) return;
3

4
    if(end - start + 1 <= 10) {
5
        insertSortRange(array,start, end);
6
        return;
7
    }
8
    // 三数取中法调用出
9
    int midNum = getMiddle(array,start,end);
10
    // 更换基准值
11
    swap(array,start,midNum);
12

13
    int privot = twop_Partition(array,start,end);
14
    quick(array,start,privot - 1);
15
    quick(array,privot + 1,end);
16
}
17
private static void insertSortRange(int[] array,int start,int end) {
18
    for (int i = start + 1; i <= end; i++) {
19
        // 定义临时变量进行存储、为下方提供比较对象
20
        int tmp = array[i];
21
        int j = i - 1;
22
        // 边找位置边移动
23
        while (j >= start && array[j] > tmp) {
24
            // 将当前值后移
25
            array[j + 1] = array[j];
26
            j--;
27
        }
28
        // 插入到正确位置
29
        array[j + 1] = tmp;
30
    }
31
}

1
    public static void mergeSort(int[] array) {
2
        mergeSortTmp(array,0,array.length - 1);
3
    }
4

5
    private static void mergeSortTmp(int[] array,int left,int right) {
6
        if (left >= right) return;
7

8
        // 1.递归分组
9
        int mid = (left + right) / 2;
10
        mergeSortTmp(array, left, mid);
11
        mergeSortTmp(array, mid + 1, right);
12

13
        // 2.合并
14
        merge(array,left,mid,right);
15
    }
16

17
    private static void merge(int[] array,int left,
18
                              int mid,int right) {
19
        // 1.创建临时数组
20
        int[] tmp = new int[right - left + 1];
21
        int k = 0;  // 记录临时数组索引
22
        int s1 = left;      // 左侧小组起始位
23
        int s2 = mid + 1;   // 右侧小组起始位
24

25
        // 2.循环比较放入
26
        while (s1 <= mid && s2 <= right) {
27
            if (array[s1] <= array[s2])
28
                tmp[k++] = array[s1++];
29
            else
30
                tmp[k++] = array[s2++];
31
        }
32
        // 3.将s1或s2剩下的填入
33
        while (s1 <= mid)
34
            tmp[k++] = array[s1++];
35
        while (s2 <= right)
36
            tmp[k++] = array[s2++];
37

38
        // 4.将临时数组拷贝入原始数组中
39
        for (int i = 0; i < k; i++) {
40
            array[i + left] = tmp[i];
41
        }
42
    }

1
    // 归并排序 非递归实现
2
public static void mergeSortNor (int[] array) {
3
    int gap = 1;    // 小组之间的间隔
4

5
    while (gap < array.length) {
6
        for (int i = 0; i < array.length; i = i + 2 * gap) {
7
            int left = i;   // 记录第一个小组左值下标
8
            int mid = left + gap - 1;   // 记录第一个小组右值下标
9
            // 防止mid数组越界
10
            if (mid >= array.length)
11
                mid = array.length - 1;
12

13
            int right = mid + gap;  // 记录第二个小组右值下标
14
            // 防止right数组越界
15
            if(right >= array.length)
16
                right = array.length - 1;
17
            merge(array,left,mid,right);
18
        }
19
        gap *= 2;
20
    }
21
}
22

23
private static void merge (int[] array,int left,
24
                              int mid,int right) {
25
    // 1.创建临时数组
26
    int[] tmp = new int[right - left + 1];
27
    int k = 0;  // 记录临时数组索引
28
    int s1 = left;      // 左侧小组起始位
29
    int s2 = mid + 1;   // 右侧小组起始位
30

31
    // 2.循环比较放入
32
    while (s1 <= mid && s2 <= right) {
33
        if (array[s1] <= array[s2])
34
            tmp[k++] = array[s1++];
35
        else
36
            tmp[k++] = array[s2++];
37
    }
38
    // 3.将s1或s2剩下的填入
39
    while (s1 <= mid)
40
        tmp[k++] = array[s1++];
41
    while (s2 <= right)
42
        tmp[k++] = array[s2++];
43

44
    // 4.将临时数组拷贝入原始数组中
45
    for (int i = 0; i < k; i++) {
46
        array[i + left] = tmp[i];
47
    }
48
}