Question

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library’s sort function for this problem.

Example:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Follow up:

  • A rather straight forward solution is a two-pass algorithm using counting sort.
  • First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.
  • Could you come up with a one-pass algorithm using only constant space?

Thinking:

  • Method1:
    • 排序算法
      • 快速排序
class Solution {
    public void sortColors(int[] nums) {
        if(nums == null) return;
        quickSort(nums, 0, nums.length - 1);
    }
    public static void quickSort(int[] nums, int low, int high){
        if(low >= high) return;
        int temp = partition(nums, low, high);
        quickSort(nums, low, temp - 1);
        quickSort(nums, temp + 1, high);
    }
    private static int partition(int[] nums, int low, int high){
        int i = low, j = high+1;
        int cmp = nums[low];
        while(true){
            while(nums[++i] <= cmp) if(i == high) break;
            while(nums[--j] > cmp) if(j == low) break;
            if(i >= j) break;
            swap(nums, i, j);
        }
        swap(nums, low, j);
        return j;
    }
    private static void swap(int[] nums, int low, int high){
        int temp = nums[low];
        nums[low] = nums[high];
        nums[high] = temp;
    }
}

二刷, 借助二刷的机会，尽量复习多种排序方法。

  1. 冒泡法 
    public void sortColors(int[] nums) {
     int len = nums.length;
     for(int i = 0; i < len - 1; i++){
             for(int j = i + 1; j < len; j++){
                 //如果遍历到的位置的值小于外部遍历的值，就交换两个值
                     if(nums[j] < nums[i]){
                             int temp = nums[i];
                             nums[i] = nums[j];
                             nums[j] = temp;
                     }
             }
     }
}
  2. 快速排序 
    class Solution {
 public void sortColors(int[] nums) {
     if(null == nums) return;
     quickSort(nums, 0, nums.length - 1);
 }
 private void quickSort(int[] nums, int low, int high){
     if(low > high) return;
     int i = partition(nums, low, high);
     quickSort(nums, low, i - 1);
     quickSort(nums, i + 1, high);
 }
 private int partition(int[] nums, int low, int high){
     int i = low, j = high + 1;
     int cmp = nums[low];
     while(true){
         while(nums[++i] <= cmp) if(i == high) break;
         while(nums[--j] > cmp) if(j == low) break;
         if(i >= j) break;
         swap(nums, i, j);
     }
     swap(nums, low, j);
     return j;
 }
 private static void swap(int[] nums, int i, int j){
     int temp = nums[i];
     nums[i] = nums[j];
     nums[j] = temp;
 }
}