Given an array of integers, sort the elements in the array in ascending order. The selection sort algorithm should be used to solve this problem.
Clarification: The input is an int[] array which is unsorted, and the output should be sorted int[]array.
Assumption: Null.
Result: Firstly we should check the corner case: if array == null || array.length <= 1, we just return the array and do nothing;
high level idea: we use two pointers, i and j, and with the iteration of i, we maintain the globalmin with the iteration of j, and swap to the first; keep all element before i are sorted.
Test: {4, 2, -3, 6, 1} is sorted to {-3, 1, 2, 4, 6}.
public class Solution {
public int[] selectionSort(int[] array) {
if (array == null || array.length <= 1) {
return array;
}
for (int i = 0; i < array.length; i++) {
int min = i;
for (int j = i + 1; j < array.length; j++) {
if (array[min] > array[j]) {
min = j;
}
}
swap(array, i, min);
}
return array;
}
private void swap(int[] array, int left, int right) {
int tmp = array[left];
array[left] = array[right];
array[right] = tmp;
}
}
Time ComplexitySpace ComplexityO(n^2)O(1)I, j 兩個for循環go over一遍arrayIn place的操作，不需要額外matintain空間
2.Merge Sort 歸併排序Given an array of integers, sort the elements in the array in ascending order. The merge sort algorithm should be used to solve this problem.
Clarification: The input is an int[] array which is unsorted, and the output should be sorted int[]array.
Assumption: Null.
Result: Firstly we should check the corner case: if array == null || array.length <= 1, we just return the array and do nothing;
high level idea: in split part, we keep finding the middle of the array, and split into two arrays, then we call the recursion function; in merge part, we merge two arrays, and sort them to one array.
Test: {4, 2, -3, 6, 1} is sorted to {-3, 1, 2, 4, 6}.
public class Solution {
public int[] mergeSort(int[] array) {
if (array == null || array.length == 0) {
return array;
}
return mergeSort(array, 0, array.length - 1);
}
private int[] mergeSort(int[] array, int left, int right) {
if (left >= right) {
return new int[] {array[left]};
}
int mid = left + (right - left) / 2;
int[] leftResult = mergeSort(array, left, mid);
int[] rightResult = mergeSort(array, mid + 1, right);
return merge(leftResult, rightResult);
}
private int[] merge(int[] leftResult, int[] rightResult) {
int[] result = new int[leftResult.length + rightResult.length];
int i = 0; int j = 0; int k = 0;
while (i < leftResult.length && j < rightResult.length) {
if (leftResult[i] < rightResult[j]) {
result[k] = leftResult[i];
i++;
k++;
}
else {
result[k] = rightResult[j];
j++;
k++;
}
}
while (i < leftResult.length) {
result[k] = leftResult[i];
i++;
k++;
}
while (j < rightResult.length) {
result[k] = rightResult[j];
j++;
k++;
}
return result;
}
}
Time ComplexitySpace ComplexityO(n) + O(nlogn) = O(nlogn)O(n)Split部分 + Merge部分recursio tree上一條直上直下的路徑和
3.Quick Sort 快速排序Given an array of integers, sort the elements in the array in ascending order. The quick sort algorithm should be used to solve this problem.
Clarification: The input is an int[] array which is unsorted, and the output should be sorted int[]array.
Assumption: Null.
Result: Firstly we should check the corner case: if array == null || array.length <= 1, we just return the array and do nothing;
high level idea: firstly, we catch a pivot randomly, move it to the right, then we keep two indexes: i and j, and do the comparison and swap, the physical meaning of them are: move all numbers smaller than the pivot to the left of i, and move all numbers larger or equal than the pivot to the right of j; finally we swap back the i and pivot, and repeat.
Test: {4, 2, -3, 6, 1} is sorted to {-3, 1, 2, 4, 6}.
public class Solution {
public int[] quickSort(int[] array) {
if (array == null || array.length == 0) {
return array;
}
quickSort(array, 0, array.length - 1);
return array;
}
private void quickSort(int[] array, int left, int right) {
if (left >= right) {
return;
}
int pivotPos = partition(array, left, right);
quickSort(array, left, pivotPos - 1);
quickSort(array, pivotPos + 1, right);
}
private int partition(int[] array, int left, int right) {
int pivotIndex = left + (int)(Math.random() * (right - left + 1));
int pivot = array[pivotIndex];
swap(array, pivotIndex, right);
int i = left;
int j = right;
while (i <= j) {
if (array[i] < pivot) {
i++;
}
else if (array[j] >= pivot) {
j--;
}
else {
swap(array, i, j);
i++;
j--;
}
}
swap(array, i, right);
return i;
}
private void swap(int[] array, int left, int right) {
int tmp = array[left];
array[left] = array[right];
array[right] = tmp;
}
}
Time ComplexitySpace ComplexityAverage O(nlogn), Worst case O(n^2)Average O(n)兩個for循環go over一遍arrayrecursio tree上一條直上直下的路徑和
4.Rainbow Sort 彩虹排序Given an array of balls, where the color of the balls can only be Red, Green or Blue, sort the balls such that all the Red balls are grouped on the left side, all the Green balls are grouped in the middle and all the Blue balls are grouped on the right side. (Red is denoted by -1, Green is denoted by 0, and Blue is denoted by 1).
Clarification: The input is an int[] array which is unsorted, and the output should be sorted int[]array.
Assumption: The input array is not null.
Result: Firstly we should check the corner case: if array == null || array.length <= 1, we just return the array and do nothing;
high level idea: we keep three indexes: i, j and k, split the array into four regions:
i = 0 -> : all letters to the left-hand side of i (not including i) are all "a"s
j = 0 -> : all letters in [i, j) (including i, but not including j) are all "b"s j is the current index
[j, k] : unexplored area (including j and k)
k = <- n - 1: all letters to the right-hand side of k (not including k) are all "c"s.
Test: {1, 0, 1, -1, 0} is sorted to {-1, 0, 0, 1, 1}.
public class Solution {
public int[] rainbowSort(int[] array) {
if (array == null || array.length <= 1) {
return array;
}
int i = 0;
int j = 0;
int k = array.length - 1;
while (j <= k) {
if (array[j] == -1) {
swap(array, i, j);
i++;
j++;
}
else if (array[j] == 0) {
j++;
}
else {
swap(array, j, k);
k--;
}
}
return array;
}
private void swap(int[] array, int left, int right) {
int tmp = array[left];
array[left] = array[right];
array[right] = tmp;
}
}
Time ComplexitySpace ComplexityO(n)O(1)兩個for循環go over一遍arrayIn place的操作，不需要額外matintain空間