算法图解-常用排序

发表于 更新于 分类于 ，

冒泡排序

冒泡排序简单来说，就是从左到右排序，如果右边较大，交换二者位置，继续遍历直到末尾得到最大值。

冒泡排序图解如下：

图中先从第一个开始，依次和右边比较，如果右边较大就进行替换，直到末尾。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private int[] data;
public void sort(){
    new Thread(() -> {
        //记录右边已经排好序的索引
        int rightIndex = data.length - 1;
        do {
            rectangles[0].setFill(Color.YELLOW);//图设置颜色、可忽略
            //从第一个开始遍历，直到右边已经排好序的索引
            for (int i = 0; i < rightIndex; i++) {
                //图 忽略
                try {
                    TimeUnit.MILLISECONDS.sleep(200);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                //这里逻辑是如果i+1 的值大于 i 那么交换二者位置
                SortUtils.exchange(data, rectangles, i, i + 1, 50);
            }
            //遍历完成后找到当前最大值后，右边已经排好序的索引左移
            rightIndex--;
        }while (rightIndex >= 0);//如果已经排好序的索引>=0表示已经拍下完毕。
        startBtn.setDisable(false);
    }).start();
}

代码中包含了图形变换代码，直接忽略即可。

wikipedia·冒泡排序

选择排序

选择排序和冒泡类似，先找到最大或者最小值。放入数组首尾。

先看图：

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public void sort() {
    //从头遍历到尾
    for (int i = 0; i < data.length; i++) {
        //记录最小索引
        int minIndex = i;

        Rectangle rectangle = rectangles[i];//忽略
        rectangle.setFill(Color.YELLOW);//忽略
        //从当前位置继续向后遍历，i 的数据表示已经做好了排序
        for (int j = i + 1; j < data.length; j++) {
            rectangles[j].setFill(Color.RED);//忽略
            try {
                TimeUnit.MILLISECONDS.sleep(200);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

            //如果向后遍历过程中，找到了最小值，所在最小索引为当前j
            if (data[minIndex] > data[j]){
                rectangles[minIndex].setFill(Color.BLUE);
                rectangles[j].setFill(Color.YELLOW);
                minIndex = j;
            } else {
                rectangles[j].setFill(Color.BLUE);
            }
        }
        //向右遍历完毕后，交换最小索引 和 i 的值
        SortUtils.changeData(data, rectangles, i, minIndex, 300);
    }
}

向右遍历，记录最小索引，放入最左边，直到数组遍历完毕。

wikipedia·选择排序

插入排序

插入排序，在遍历过程中，保证左边已经是排好序，遍历的下一个数需要在已经排序的数组中找到自己的位置。
动图如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public void sort() {
    //从左遍历数组
    for (int i = 0; i < data.length; i++) {

        rectangles[i].setFill(Color.RED);
        //遍历节点i左边数组，目的是为了找到i节点在左侧已经排好序的数组中所在位置
        int insertIndex = i - 1;
        for (; insertIndex >= 0; insertIndex--) {
            try {
                TimeUnit.MILLISECONDS.sleep(300);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            //如果从i节点反向遍历过程中，下一个节点大于当前节点那么交换二者位置
            //因为内循环是从i-1节点进行，比较的是i-1的左侧节点，如果左侧节点较大，那么交换位置
            if (data[insertIndex] > data[insertIndex + 1]) {
                SortUtils.changeData(data, rectangles, insertIndex, insertIndex + 1, 100);
            } else {
                //如果左侧节点较小那么跳出内循环
                break;
            }
        }
        rectangles[insertIndex + 1].setFill(Color.YELLOW);
    }
}

上述代码中，先从左侧开始遍历，然后遍历中的节点开始向右比较，直到直到正确的位置。

wikipedia·插入排序

并归排序

并归排序是一种分治算法，把一个大数组先合并为一个个小数组，对小数组进行排序，之后再把小数组进行合并排序，直到最终合并为一个排好的大数组。在并归排序中需要引入额外的空间。

上述图中可以看出，先是把数组进行对半分，直到划分为最小数组长度1~2，然后小数组排序后，在合并大数组。对于并归排序中可以采用Java中Fork/Join进行加速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
public void sort() throws Exception {
    tmpRectangles = new Rectangle[data.length];

    //构造一个新的数组，用于临时存储数据
    int[] tmpArr = new int[data.length];
    System.out.println(Arrays.toString(data));
    //递归调用
    sortRecursive(data, tmpArr, 0, tmpArr.length - 1);
    System.out.println(Arrays.toString(data));

}

/**
    * @param data 原数组
    * @param result 临时数组
    * @param start 数组排序开始索引
    * @param end 数组排序结束索引
    * @throws Exception
    */
public void sortRecursive(int[] data, int[] result, int start, int end) throws Exception {
    //如果开始索引大于结束索引，表示已经拆分为最小了，直接返回
    if (start >= end){
        return;
    }
    //计算数组中间值，用于拆分排序
    int mid = ((end - start) >> 1) + start;
    //拆分数组起始值为start ~ mid  | mid + 1 ~ end
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    //对拆分的数组进行递归拆分排序
    sortRecursive(data, result, start1, end1);
    sortRecursive(data, result, start2, end2);

    //这里表示递归拆分完毕，开始排序
    int i = start;
    //先两个数组取值
    Rectangle rectangle;
    //排序拆分的两个数组，核心原理就是从数组中取值比较后放入临时数组
    while (start1 <= end1 && start2 <= end2){
        //下面逻辑可以写为如下的一句话，为了图形展示，进行了拆分
//            result[i++] = data[start1] <= data[start2]? data[start1++]: data[start2++];
        //如果左侧值<=右侧的值，那么取左侧值到临时数组中，同时左侧角标+1，表示标记左侧取值索引
        if (data[start1] <= data[start2]){
            rectangle = rectangles[start1];
            result[i] = data[start1];
            tmpRectangles[i] = rectangles[start1];
            start1++;
        } else {
            //否则取右侧的值，同时右侧角标+1
            rectangle = rectangles[start2];
            result[i] = data[start2];
            tmpRectangles[i] = rectangles[start2];
            start2++;
        }
        //移动到上面，重新确定位置
        rectangle.setFill(Color.RED);
        TimeUnit.MILLISECONDS.sleep(100);
        AnchorPane.setBottomAnchor(rectangle, anchorPane.getHeight()/2);
        TimeUnit.MILLISECONDS.sleep(100);
        AnchorPane.setLeftAnchor(rectangle, BORDER_WIDTH * (i + 1) + i * rectangle.getWidth());

        //临时数组存入的值+1，表示已经存入的值位置
        i++;
    }
    //这里如果第二个数组取值完毕，把数组1中值全部移动到临时数组中
    while (start1 <= end1){
        rectangle = rectangles[start1];

        result[i] = data[start1];
        tmpRectangles[i] = rectangles[start1];

        rectangle.setFill(Color.RED);
        TimeUnit.MILLISECONDS.sleep(100);
        AnchorPane.setBottomAnchor(rectangle, anchorPane.getHeight()/2);
        TimeUnit.MILLISECONDS.sleep(100);
        AnchorPane.setLeftAnchor(rectangle, BORDER_WIDTH * (i + 1) + i * rectangle.getWidth());

        i++;
        start1++;

    }
    //这里表示如果第一个数组取值完毕，把数组2中值全部移动到临时数组中
    while (start2 <= end2){
        rectangle = rectangles[start2];

        result[i] = data[start2];
        tmpRectangles[i] = rectangles[start2];

        rectangle.setFill(Color.RED);
        TimeUnit.MILLISECONDS.sleep(100);
        AnchorPane.setBottomAnchor(rectangle, anchorPane.getHeight()/2);
        TimeUnit.MILLISECONDS.sleep(100);
        AnchorPane.setLeftAnchor(rectangle, BORDER_WIDTH * (i + 1) + i * rectangle.getWidth());

        i++;
        start2++;
    }
    //把临时数组中数据移动到原数组中
    for (int j = start; j <= end; j++) {
        data[j] = result[j];
        rectangles[j] = tmpRectangles[j];
        rectangle = rectangles[j];
        TimeUnit.MILLISECONDS.sleep(100);
        rectangle.setFill(Color.YELLOW);
        AnchorPane.setBottomAnchor(rectangle, 0d);
        AnchorPane.setLeftAnchor(rectangle, BORDER_WIDTH * (j + 1) + j * rectangle.getWidth());

    }
}

并归代码中无关代码较多。很多图形移动的逻辑。需要进行进一步封装。

上述代码中就是通过不断的拆分数组，然后对拆分的数组进行排序，只对排序的数组进一步排序直到结束。其中一部分逻辑就是从已经排序好的两个数组进行合并，也就简单的从两个数组中取值进行比较，直到某个数组值取值完毕，然后对移动另一个数组中的数剧到末尾。

wikipedia·归并排序

快速排序

快速排序基本原理是，先从数组中随机找一个基准，然后把小于改基准的值放入左边，大于改基准的值放入右边。然后对左右两边的数组进行递归同样的方法，找到随机值，小的放到左边，大的放到右边。


图中，黑色表示基准，先把获取的基准放入最右边，从左到右遍历，记录放入左侧的位置，如果遍历过程中值小于基准值，那么把该值替换到左侧记录的位置，位置左移，继续遍历，直到末尾，把基准插入左侧记录的位置。继续递归，直到结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public void sort() throws Exception {
    System.out.println(Arrays.toString(data));
    //开始排序
    sort(data, 0, data.length - 1);
    System.out.println(Arrays.toString(data));
}

/**
    *
    * @param data 排序数组
    * @param leftIndex 数组左侧索引
    * @param rightIndex 右侧索引
    * @throws Exception
    */
public void sort(int[] data, int leftIndex, int rightIndex)throws Exception{
    //如果支持索引大于右侧索引，表已经递归结束
    if (leftIndex >= rightIndex){
        if (rightIndex < 0){
            rectangles[leftIndex].setFill(Color.YELLOW);
        }else {
            rectangles[rightIndex].setFill(Color.YELLOW);
        }
        return;
    }
    //获取基准索引，存储采用的事中间值，也可以采用随机数
    int pivot = (leftIndex + rightIndex)/2;
    //交换基准元素到最后
    rectangles[pivot].setFill(Color.BLACK);
    SortUtils.changeData(data, rectangles, pivot, rightIndex, 200);

    //记录交换索引的位置，用于交换小于基准的值，默认为最左侧索引
    int swapIndex = leftIndex;
    //从左遍历到右
    for (int i = leftIndex; i < rightIndex; i++) {
        rectangles[i].setFill(Color.RED);
        TimeUnit.MILLISECONDS.sleep(200);
        //如果遍历的值小于基准，那么把该值交换到之前记录的左侧索引位置，然后索引位置+1
        if (data[i] <= data[rightIndex]){
            SortUtils.changeData(data, rectangles, swapIndex, i, 200);
            rectangles[i].setFill(Color.RED);
            rectangles[swapIndex].setFill(Color.BLUE);
            swapIndex++;
        }
        rectangles[i].setFill(Color.BLUE);
    }
    //一次遍历完成后，把最右侧的值（基准）替换到记录的索引位置，此时，左侧数据<=基准，右侧>基准
    SortUtils.changeData(data, rectangles, swapIndex, rightIndex, 200);
    rectangles[swapIndex].setFill(Color.YELLOW);
    //递归基准左右两侧数组
    sort(data, leftIndex, swapIndex - 1);
    sort(data, swapIndex + 1, rightIndex);
}

wikipedia·快速排序

堆排序

堆排序的要点在于，先对数组构造一个完全二叉树，之后对二叉树取最高点，之后重新构造二叉树，重复上述步骤，直到取值完毕。
需要用的的知识点：

  • 父节点i的左子节点在位置 (2i+1);
  • 父节点i的右子节点在位置 (2i+2);
  • 子节点i的父节点在位置 floor((i-1)/2);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
//用于方便画图
class GraphVo {
    int num;
    StackPane stackPane;
    Text text;
    Circle circle;
}
GraphVo[] graphVos;
private void sort() throws Exception {
    //获取最后的索引
    int lastIndex = graphVos.length - 1;
    //计算最后一个父节点，因为不需要从子节点开始
    int lastParentIndex = lastIndex >> 1;
    toStr();
    //构造一个最大二叉堆
    for (int i = lastParentIndex; i >= 0; i--) {
        maxHeap(i, lastIndex);
    }
    for (GraphVo graphVo : graphVos) {
        graphVo.circle.setFill(Color.AZURE);
    }
    TimeUnit.SECONDS.sleep(2);
    toStr();
    //从二叉堆中取值，放入数组末尾，之后重新构造新的最大二叉堆
    for (int i = lastIndex; i >= 0; i--) {
        graphVos[0].circle.setFill(Color.YELLOW);
        //交换第一个到末尾
        swap(0, i);
        //重新构造最大二叉堆，已经交换到末尾的数除外，因为根节点已经变更，所以需要重新从根节点构造二叉堆
        maxHeap(0, i - 1);
    }
    toStr();
}

private void maxHeap(int parentIndex, int lastIndex) throws Exception {
    //计算父节点左节点 2 * i + 1
    int leftI = (parentIndex << 1) + 1;
    //计算父节点右节点
    int rightI = leftI + 1;
    //如果左节点已经超过最大索引，那么返回，表示已经是最后一个父节点了
    if (leftI > lastIndex) return;
    //知道左右索引最大值，默认为左侧索引
    int maxIndex = leftI;
    //如果右侧索引没超过最大索引，且右侧的值为最大值，那么最大值索引为右边
    if (rightI <= lastIndex && graphVos[rightI].num > graphVos[leftI].num) {
        maxIndex = rightI;
    }
    graphVos[parentIndex].circle.setFill(Color.RED);
    TimeUnit.MILLISECONDS.sleep(100);
    //比较父节点和最大子节点值，如果子节点大，那么需要交换父子节点，
    if (graphVos[maxIndex].num > graphVos[parentIndex].num) {

        swap(maxIndex, parentIndex);
        //因为父节点发生了变动，那么变动的子节点需要重新构造二叉堆，继续向下构造
        maxHeap(maxIndex, lastIndex);
    }
}

附赠python3的排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
def bubble_sort(nums):
    end_index = len(nums) - 1
    for i in range(end_index, 0, -1):
        for j in range(0, i):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    return nums


def select_sort(nums):
    end_index = len(nums) - 1
    for i in range(end_index, 0, -1):
        max_index = 0
        for j in range(0, i):
            if nums[j + 1] > nums[max_index]:
                max_index = j + 1
        nums[i], nums[max_index] = nums[max_index], nums[i]
    return nums


def insert_sort(nums):
    for i in range(len(nums)):
        for j in range(i, 0, -1):
            if nums[j] < nums[j - 1]:
                nums[j], nums[j - 1] = nums[j - 1], nums[j]
            else:
                break
    return nums


def merge_sort(nums):
    def merge_re(nums, tmp_nums, start, end):
        if start >= end:
            return
        mid = (start + end) >> 1
        merge_re(nums, tmp_nums, start, mid)
        merge_re(nums, tmp_nums, mid + 1, end)

        left = start
        right = mid + 1
        tmp_i = left
        while True:
            if left <= mid and right <= end:
                if nums[left] <= nums[right]:
                    tmp_nums[tmp_i] = nums[left]
                    left += 1
                else:
                    tmp_nums[tmp_i] = nums[right]
                    right += 1
                tmp_i += 1
            else:
                break

        while True:
            if left <= mid:
                tmp_nums[tmp_i] = nums[left]
                left += 1
                tmp_i += 1
            else:
                break

        while True:
            if right <= end:
                tmp_nums[tmp_i] = nums[right]
                right += 1
                tmp_i += 1
            else:
                break

        for i in range(start, end + 1):
            nums[i] = tmp_nums[i]

    merge_re(nums, [0] * len(nums), 0, len(nums) - 1)
    return nums


def quick_sort(nums):
    def quick_re(nums, left, right):
        if left >= right:
            return
        mid = (right + left) >> 1
        nums[mid], nums[right] = nums[right], nums[mid]
        mid = left
        for i in range(left, right):
            if nums[i] <= nums[right]:
                nums[mid], nums[i] = nums[i], nums[mid]
                mid += 1
        nums[mid], nums[right] = nums[right], nums[mid]
        quick_re(nums, left, mid - 1)
        quick_re(nums, mid + 1, right)

    quick_re(nums, 0, len(nums) - 1)
    return nums


def heap_sort(nums):
    def max_heap(nums, parent, last):
        left = (parent << 1) + 1
        right = left + 1
        if left > last:
            return
        max_i = left
        if right <= last and nums[right] > nums[left]:
            max_i = right
        if nums[parent] < nums[max_i]:
            nums[parent], nums[max_i] = nums[max_i], nums[parent]
            max_heap(nums, max_i, last)

    last_i = len(nums) - 1
    last_p = (last_i >> 1) - 1
    for i in range(last_p, -1, -1):
        max_heap(nums, i, last_i)

    for i in range(last_i, 0, -1):
        nums[0], nums[i] = nums[i], nums[0]
        max_heap(nums, 0, i - 1)
    return nums


def random_int_list(start, stop, length):
    import random
    start, stop = (int(start), int(stop)) if start <= stop else (int(stop), int(start))
    length = int(abs(length)) if length else 0
    random_list = []
    for i in range(length):
        random_list.append(random.randint(start, stop))
    return random_list


def now():
    import time
    return int(round(time.time() * 1000))

在上述图形化中，因为为了展现较好的效果，做了图形移动。如果不需要由移动效果，可以直接保存数组，在每次数组变动后，清除图形，然后依据变化后的数组重新画图，那么相对而言更为简单。

wikipedia·堆排序

各种排序复杂度：

  • 常用排序算法稳定性、时间复杂度分析

源码地址：https://github.com/whhxz/graphic-algorithm