Home Computer Science Java Algorithm

464 · Sort Integers II - LintCode

# Description

Given an integer array, sort it in ascending order in place. Use quick sort, merge sort, heap sort or any O(nlogn) algorithm.

# Example

Example1:

Input: [3, 2, 1, 4, 5], 
Output: [1, 2, 3, 4, 5].

Example2:

Input: [2, 3, 1], 
Output: [1, 2, 3].

# Note

（用快速排速做這一題）

# 快排的基本三點：

  1. 選擇 pivot
  2. 劃分 2 個區域，長度不需相等（partition)
  3. 递歸處理子問題

# 如何把數組分為兩部份 (partition)

  • 兩個指針，一個在頭，一個在尾
  • left 指針向右移，直到 nums[left] >= pivot 就停下
    • 意思是：因為 nums[left] 小於 pivot，已經在對的區域裡了，接下來不需要進行交換。
  • right 指針向左移，直到 nums[right] <= pivot 就停下
  • 交換兩個指針的數
  • 回到第二步，直到兩個指針相遇

# 兩個子問題的邊界

  • start, right
  • left, end
    當循環結束時，right 一定小於 left
start = 4 的 index
end = nums.length - 1; //end = 9 的 index
e.g:
[ 4 [ right ]  [pivot]  [ left ] 9 ]

# Code

time complexity :  O(N log(N))

public class Solution {
	private void sorting(int[] nums) {
		if (nums == null) return;
		quickSort(nums, 0, nums.length - 1);
	}
	private void quickSort(int[] nums, int start, int end) {
		if (start >= end) return;
		int left = start, right = end;
		int pivot = nums[start + (end - start) / 2];
		while (left <= right) {
			while (left <= right && nums[left] < pivot) {
				left++;
			}
			while (left <= right && nums[right] > pivot) {
			right--;
			}
			if (left <= right) {
				int temp = nums[left];
				nums[left] = nums[right];
				nums[right] = temp;
				left++;
				right--;
			}
		}
		quickSort(nums, start, right);
		quickSort(nums, left, end);
	}
}
算法學習的網站：
第 5 节 双路快排 | 算法吧 (suanfa8.com)