AP最后复习-Several Sorting Methods in A Glance

时间不多，下午就要考试了，基础的知识相信大家已经有掌握，那么最后可以临时抱佛脚的就是比较关键的 排序方法 了。下面给出AP最常考到的三种排序方法的代码实现，大家可以在看的同时想一想这三种方法的实现原理以及机制。


PS：代码实现是我昨晚默写一次过出来的。在保证实习机制核心原理不改变的情况下，代码的优化其实非常不足（比如一个值被 computed 多次而不是存储为变量）。所以看看排序就好。

I: 选择排序 Selection Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//核心在于一遍遍的找出第1，第2...第n小的数放在1,2...n位置
public static void selection_sort(int[] nums)
{
    for (int i = 0; i < nums.length - 1 ; i++)
    {
        int min = nums[i];
        int pos = i;

        for (int j = i; j < nums.length; j++)
        {
            if (nums[j] <= min) {
                min = nums[j];
                pos = j;
            }
        }

        nums[pos] = nums[i];
        nums[i] = min;

        System.out.println(Arrays.toString(nums));
    }
}

II: 冒泡排序 Bubble Sort


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*难点在于双循环中两个循环一个向前一个向后。目的是每一轮循环将一个最小 值推到前面的位置。
*/
public static void bubble_sort(int [] nums)
{
    for (int i = 0; i < nums.length; i++)
    {
        for (int j = nums.length - 1; j > i ; j--)
        {
            int temp = nums[j];

            if (nums[j-1] > nums[j])
            {
                temp = nums[j-1];
                nums[j-1] = nums[j];
            }

            nums[j] = temp;
        }
        System.out.println(Arrays.toString(nums));
    }
}

III: 快速排序 Quick Sort


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
//核心在于将所有大于一个中心值（也就是pivot，一般取数组第一个）放到一边，小于它的放在另一边。每一次循环/递归的结果可以贡献给下一轮，所以效率高
public static void quick_sort(int [] nums, int start, int end)
{
    if (start > end)
        return;

    int i = start;
    int j = end;
    int pivot = nums[start];
    int pos = start;

    while (i < j)
    {
        while (i < j && nums[j] > pivot)
            j--;

        while (i < j && nums[i] <= pivot)
            i++;

        if (i < j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }

    nums[start] = nums[j];
    nums[j] = pivot;

    quick_sort(nums, start, j - 1);
    quick_sort(nums, j + 1, end);
}

Merge Sort是没有时间写的…就记住Merge Sort使用了分而治之的方法（divide and conquer）然后逐个击破吧…