selection sort

merge sort

quick sort

bucket sort

quick sort

public class Solution {
  public int[] quickSort(int[] array) {
    // Write your solution here
    if (array == null || array.length <= 1) {
      return array;
    }

    partition(array, 0, array.length -1);
    return array;
  }

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

    int mid = left + (right - left) / 2;
    int pivot = array[mid];
    int start = left;
    int end  = right;
    while (start <= end) {
      // move the start pointer to the index which larger than pivot
      // move the end pointer to the index which less than pivot

      while(start <= end && array[start] < pivot) {
        start++;
      }
      while(start <= end && array[end] > pivot) {
        end--;
      }

      if (start <= end) {
        swap(array, start++, end--);
      }
    }

    // after this round, the pivot should be on the correct location accroding to the sorting sequence
    // end pointer is its index
    // the unprocessed area will be left - end, start - right

    partition(array, left, end);
    partition(array, start, right);
  }
  private void swap(int[] array, int left, int right) {
    int temp = array[left];
    array[left] = array[right];
    array[right] = temp;
  }
}

merge sort

public class Solution {
  public int[] mergeSort(int[] array) {
    // Write your solution here.
    if (array == null || array.length <= 1) {
      return array;
    }
    int[] helperArr = new int[array.length];
    mergeSort(array, 0, array.length - 1, helperArr);
    return array;
  }

  private void mergeSort(int[] array, int start, int end, int[] helperArr) {
    if (start >= end) {
      return;
    }

    int mid = start + (end - start) / 2;
    mergeSort(array, start, mid, helperArr);
    mergeSort(array, mid + 1, end, helperArr);
    merge(array, start, mid, end, helperArr);
  }

  private void merge(int[] array, int start, int mid, int end, int[] helperArr) {

    for (int i = start; i <= end; i++) {
      helperArr[i] = array[i];
    }

    int left = start;
    int right = mid + 1;

    while(left <= mid && right <= end) {
      if (helperArr[left] <= helperArr[right]) {
        array[start++] = helperArr[left++];
      } else {
        array[start++] = helperArr[right++];
      }
    }

    while(left <= mid) {
      array[start++] = helperArr[left++];
    }
    while(right <= end) {
      array[start++] = helperArr[right++];
    }
  }
}

selection sort

void sort(int arr[])
    {
        int n = arr.length;

        // One by one move boundary of unsorted subarray
        for (int i = 0; i < n-1; i++)
        {
            // Find the minimum element in unsorted array
            int min_idx = i;
            for (int j = i+1; j < n; j++)
                if (arr[j] < arr[min_idx])
                    min_idx = j;

            // Swap the found minimum element with the first
            // element
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }

bucket sort

void bucketSort(float arr[], int n)
    {
        // 1) Create n empty buckets
        vector<float> b[n];

        // 2) Put array elements in different buckets
        for (int i=0; i<n; i++)
        {
            int bi = n*arr[i]; // Index in bucket
            b[bi].push_back(arr[i]);
        }

        // 3) Sort individual buckets
        for (int i=0; i<n; i++)
            sort(b[i].begin(), b[i].end());

        // 4) Concatenate all buckets into arr[]
        int index = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < b[i].size(); j++)
                arr[index++] = b[i][j];
    }