Skip to content

Sort Algorithm Summary

Jump to bottom
Xin Wan edited this page Oct 25, 2019 · 4 revisions

Quick Sort

两个挡板i，j，三个区间 a), b) c)的思想： a) [0...i）: i的左侧（不包含i）全部为比pivot小的数 b）［i，j］：i 和j之间为未知探索区域 c）（j...n - 1): j的右侧（不包含j）全部为比pivot大或等于的数

public class Solution {
  public int[] quickSort(int[] array) {
    if (array == null || array.length == 0) {
      return array;
    }
    
    quickSortHelper(array, 0, array.length - 1);
    return array;
  }
  
  private void quickSortHelper(int[] array, int left, int right) {
    if (left >= right) {
      return;
    }
    
    int pivot = partition(array, left, right);
    
    quickSortHelper(array, left, pivot - 1);
    quickSortHelper(array, pivot + 1, right);
  }
  
  private int partition(int[] array, int left, int right) {
    int pivot = array[right];
    int l = left;
    int r = right - 1;
    
    while (l <= r) {
      if (array[l] < pivot) {
        l++;
      } else if (array[r] >= pivot) {
        r--;
      } else {
        swap(array, l, r);
      }
    }
    
    swap(array, l, right);
    
    return l; // notice it should return l rather than pivot since pivot is value and l is index.
  }
  
  private void swap(int[] array, int left, int right) {
    int tmp = array[left];
    array[left] = array[right];
    array[right] = tmp;
  }
}

常见题目

  • Array Shuffling: Given an array with integers, move all 0s to the right-end of the array. (2个挡板，3个区域，相向而行)
  • Rainbow sort (abcccabbcbbacaa -> aaaa bbbbb ccccc) (3个挡板，4个区域， 同向 ＋ 相向而行) Example: aaaaaa bbbbbb XXXXX Cccccc i j k [j,k]为未知探索区域

Selection Sort

The solution is: 每次for-loop找到最小值的位置，然后与其实位置进行交换。

  • The first attempt
public void selectionSort(intp[] array) {
	if (array == null || array.length == 0) {
		return;
	}

	int minPos = -1;
	for (int i = 0; i < array.length; i++) {
		for (int j = i; j < array.length; j++) {
			if (i == j) {
				minPos = i;
			} else if (array[minPos] > array[j]) {
				minPos = j;
			}
		}

		swap(array, minPos, i);
	}
}

private void swap(int[] array, int x, int y) {
	int tmp = array[x];
	int array[x] = array[y];
	array[y] = tmp;
}

The bad thing is the following, which is unnecessary:

int minPos = -1;
if (i == j) {
    minPos = i;
}
  • The second attempt
public void selectionSort(intp[] array) {
	if (array == null || array.length == 0) {
		return;
	}

	for (int i = 0; i < array.length; i++) {

		int minPos = i;
		for (int j = i + 1; j < array.length; j++) {
			if (array[minPos] > array[j]) {
				minPos = j;
			}
		}

		swap(array, minPos, i);
	}
}

private void swap(int[] array, int x, int y) {
	int tmp = array[x];
	int array[x] = array[y];
	array[y] = tmp;
}

Merge Sort

I think mergeSort algorithm should be inplace sort algorithm. Time: O(nlogn) Space: O(n)

public class MergeSortClass {

	private int[] helper;
	public void mergeSort(int[] array) {
		if (array == null || array.length == 0) {
			return;
		}
		helper = new int[array.length];
		mergeSortHelper(array, 0, array.length - 1);
	}

	private void mergeSortHelper(int[] array, int left, int right) {
		if (right <= left) {
			return;
		}

		int mid = (right - left) / 2 + left;
		mergeSortHelper(array, left, mid);
		mergeSortHelper(array, mid + 1, right);

		merge(array, left, mid + 1, right);
	}

	private void merge(int[] array, int left, int mid, int right) {
		for (int i = left; i <= right; i++) {
			helper[i] = array[i];
		}

		int first = left;
		int second = mid;
		int pos = left;

		while (first <= mid && second <= right) {
			if (helper[first] < helper[second]) {
				array[pos++] = helper[first++];
			} else {
				array[pos++] = helper[second++];
			}
		}

		while (first <= mid) {
			array[pos++] = helper[first++];
		}

		while (second <= right) {
			array[pos++] = helper[second++];
		}
	}
}

Without static Helper[]

public class Solution {
  
  public int[] mergeSort(int[] array) {
    if (array == null || array.length == 0) {
      return array;
    }
    mergeSortHelper(array, 0, array.length - 1);
    return array;
  }

  private void mergeSortHelper(int[] array, int left, int right) {
    if (left >= right) {
      return;
    }

    int mid = left + (right - left) / 2;
    mergeSortHelper(array, left, mid);
    mergeSortHelper(array, mid + 1, right);
    merge(array, left, mid, right);
  }

  private void merge(int[] array, int left, int mid, int right) {
    int[] helper = new int[right - left + 1];
    int first = left;
    int second = mid + 1;
    int pos = 0;
    while (first <= mid && second <= right) {
      if (array[first] < array[second]) {
        helper[pos++] = array[first++];
      } else {
        helper[pos++] = array[second++];
      }
    }

    while (first <= mid) {
      helper[pos++] = array[first++];
    }

    while (second <= right) {
      helper[pos++] = array[second++];
    }

    for (int i = 0; i < helper.length; i++) {
      array[left + i] = helper[i];
    }
  }
}

经典题型

  • Sort A1B2C3D4 -> ABCD1234
  • (Advanced) Sort ABCD1234 -> A1B2C3D4 The idea: ABCD | 1234 AB CD 12 34 AB 21DC 34 AB 12 CD 34 -> AB12 CD34 Sort中存在两次reverse，这道题中不需要merge，merge 就是保持两个排好array的既定顺序
public class MergeSortSample {
	public static void main(String[] args) {
		MergeSortSample sample = new MergeSortSample();

		String input = "ABCD1234";
		System.out.println("Before MergeSort: " + input);
		System.out.println("Result: " + sample.mergeSort(input));
	}

	private String mergeSort(String input) {
		char[] array = new char[input.length()];
		for (int i = 0; i < array.length; i++) {
			array[i] = input.charAt(i);
		}

		mergeSortHelper(array, 0, array.length - 1);

		String result = "";
		for (char c : array) {
			result += c;
		}

		return result;
	}

	private void mergeSortHelper(char[] array, int left, int right) {
		if (left >= right) {
			return;
		}

		int len = right - left + 1;

		int first = left + len / 4;
		int second = left + len * 2 / 4;
		int third = left + len * 3 / 4;

		reverse(array, first, third - 1);
		reverse(array, first, second - 1);
		reverse(array, second, third - 1);

		mergeSortHelper(array, left, second - 1);
		mergeSortHelper(array, second, right);

	}

	private void reverse(char[] array, int left, int right) {
		while (left < right) {
			char tmp = array[left];
			array[left] = array[right];
			array[right] = tmp;
			left++;
			right--;
		}
	}

}
  1. Instead of sorting the number directly, it will sort their index.
  2. mergeSort method 没有什么变化， merge method 变化很大，left side的元素和right side 的元素会相互比较，最终结果存到count［］中。
class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> result = new ArrayList<Integer>();
        
        if (nums == null || nums.length == 0) {
            return result;
        }
        
        int[] index = new int[nums.length];
        int[] count = new int[nums.length];
        
        for (int i = 0; i < nums.length; i++) {
            index[i] = i;
        }
        mergeSort(nums, index, count, 0, nums.length - 1);
        
        for (int c : count) {
            result.add(c);
        }
        
        return result;
    }
    
    private void mergeSort(int[] num, int[] index, int[] count, int left, int right) {
        if (left >= right) {
            return;
        }
        
        int mid = (right - left) / 2 + left;
        mergeSort(num, index, count, left, mid);
        mergeSort(num, index, count, mid + 1, right);
        
        merge(num, index, count, left, mid, right);
    }
    
    private void merge(int[] num, int[] index, int[] count, int left, int mid, int right) {
        int[] tmp = new int[right - left + 1];
        
        int leftIdx = left;
        int rightIdx = mid + 1;
        int idx = 0;
        int rightCount = 0;
        while (leftIdx <= mid && rightIdx <= right) {
            if (num[index[leftIdx]] > num[index[rightIdx]]) {
                tmp[idx] = index[rightIdx++];
                rightCount++;
            } else {
                tmp[idx] = index[leftIdx];
                count[index[leftIdx++]] += rightCount;
            }
            idx++;
        }
        
        while (leftIdx <= mid) {
            tmp[idx] = index[leftIdx];
            count[index[leftIdx]] += rightCount;
            idx++;
            leftIdx++;
        }
        
        while (rightIdx <= right) {
            tmp[idx++] = index[rightIdx++];
        }
        
        for (int i = 0; i < right - left + 1; i++) { //Notice it is right - left + 1 rather than right - left.
            index[i + left] = tmp[i];
        }
    }
}

Bubble Sort

Bucket Sort

Need to learn

Clone this wiki locally