Classical Sorting Algorithms // JAVA // Some with detailed explanations
1. Quick Sort\n\n\tclass Solution {\n\n\t\tpublic int[] sortArray(int[] nums) {\n\t\t\tquickSort(nums, 0, nums.length - 1);\n\t\t\treturn nums;\n\t\t}\n\n\t\tpu
**1. Quick Sort**\n```\n\tclass Solution {\n\n\t\tpublic int[] sortArray(int[] nums) {\n\t\t\tquickSort(nums, 0, nums.length - 1);\n\t\t\treturn nums;\n\t\t}\n\n\t\tpublic void quickSort(int[] nums, int start, int end) {\n\t\t\t// if the start index is larger or equal to the end index, the sort of the subarray is finished\n\t\t\tif (start >= end) {\n\t\t\t\treturn;\n\t\t\t}\n\t\t\tint pivot = partition(nums, start, end);\n\t\t\t// recursively sort the subarray\n\t\t\tquickSort(nums, start, pivot - 1);\n\t\t\tquickSort(nums, pivot + 1, end);\n\t\t}\n\n\t\t/** \n\t\t *  This function takes last element as pivot, places the pivot element at its correct position in sorted array,\n\t\t *  and places all smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot \n\t\t **/\n\t\tpublic int partition(int[] nums, int start, int end) {\n\t\t\t// choose the number in the middle as the base and swap it with the first number in the subarray\n\t\t\tswap(nums, start, start + (end - start) / 2);\n\t\t\tint base = nums[start];\n\t\t\t// swap every number that is less than the base to the front of the subarray\n\t\t\tint i = start + 1;\n\t\t\tint j = i;\n\t\t\twhile (i <= end) {\n\t\t\t\tif (nums[i] < base) {\n\t\t\t\t\tswap(nums, i, j++);\n\t\t\t\t}\n\t\t\t\ti++;\n\t\t\t}\n\t\t\t// after the iteration the numbers from index start+1 to index j-1 are less than the base\n\t\t\t// swap the number on index j-1 with the base\n\t\t\t// the first j-2 numbers are less than the base\n\t\t\t// the number on index j-1 is the base\n\t\t\t// numbers after index j-1 are larger or equal to the base\n\t\t\tswap(nums, j - 1, start);\n\t\t\treturn j - 1;\n\t\t}\n\n\t\tprivate void swap(int[] nums, int i, int j) {\n\t\t\tint temp = nums[i];\n\t\t\tnums[i] = nums[j];\n\t\t\tnums[j] = temp;\n\t\t}\n\n\t}\n```\n\n**2. Merge Sort**\n```\n\tclass Solution {\n\n\t\tpublic int[] sortArray(int[] nums) {\n\t\t\tmergeSort(nums, 0, nums.length - 1);\n\t\t\treturn nums;\n\t\t}\n\n\t\tpublic void mergeSort(int[] nums, int start, int end) {\n\t\t\t// if the start index is larger or equal to the end index, the sort of the subarray is finished\n\t\t\tif (start >= end) {\n\t\t\t\treturn;\n\t\t\t}\n\t\t\tint mid = start + (end - start) / 2;\n\t\t\tmergeSort(nums, start, mid);\n\t\t\tmergeSort(nums, mid + 1, end);\n\t\t\tmerge(nums, start, end);\n\t\t}\n\n\t\tpublic void merge(int[] nums, int start, int end) {\n\t\t\tint mid = start + (end - start) / 2;\n\t\t\tint[] temp = new int[end - start + 1];\n\t\t\tint leftStart = start;\n\t\t\tint leftEnd = mid;\n\t\t\tint rightStart = mid + 1;\n\t\t\tint rightEnd = end;\n\t\t\tint i = 0;\n\t\t\twhile (leftStart <= leftEnd && rightStart <= rightEnd) {\n\t\t\t\tif (nums[leftStart] <= nums[rightStart]) {\n\t\t\t\t\ttemp[i] = nums[leftStart];\n\t\t\t\t\tleftStart++;\n\t\t\t\t} else {\n\t\t\t\t\ttemp[i] = nums[rightStart];\n\t\t\t\t\trightStart++;\n\t\t\t\t}\n\t\t\t\ti++;\n\t\t\t}\n\t\t\twhile (leftStart <= leftEnd) {\n\t\t\t\ttemp[i] = nums[leftStart];\n\t\t\t\tleftStart++;\n\t\t\t\ti++;\n\t\t\t}\n\t\t\twhile (rightStart <= rightEnd) {\n\t\t\t\ttemp[i] = nums[rightStart];\n\t\t\t\trightStart++;\n\t\t\t\ti++;\n\t\t\t}\n\t\t\tfor (int j = 0; j < i; j++) {\n\t\t\t\tnums[start + j] = temp[j];\n\t\t\t}\n\t\t}\n\n\t\tprivate void swap(int[] nums, int i, int j) {\n\t\t\tint temp = nums[i];\n\t\t\tnums[i] = nums[j];\n\t\t\tnums[j] = temp;\n\t\t}\n\n\t}\n```\n\n**3. Bubble Sort [Time Limit Exceeded]**\n```\n\tclass Solution {\n\n\t\tpublic int[] sortArray(int[] nums) {\n\t\t\tfor (int i = 0; i < nums.length - 1; i++) {\n\t\t\t\tfor (int j = 0; j < nums.length - i - 1; j++) {\n\t\t\t\t\tif (nums[j + 1] < nums[j]) {\n\t\t\t\t\t\tswap(nums, j, j + 1);\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t}\n\t\t\treturn nums;\n\t\t}\n\n\t\tprivate void swap(int[] nums, int i, int j) {\n\t\t\tnums[i] = nums[i] ^ nums[j];\n\t\t\tnums[j] = nums[i] ^ nums[j];\n\t\t\tnums[i] = nums[i] ^ nums[j];\n\t\t}\n\n\t}\n```\n\n**4. Selection Sort [Time Limit Exceeded]**\n```\n\tpublic class Solution {\n\n\t\tpublic int[] sortArray(int[] nums) {\n\t\t\tif (nums.length <= 1) {\n\t\t\t\treturn nums;\n\t\t\t}\n\t\t\tint[] res = new int[nums.length];\n\t\t\tInteger size = 0;\n\t\t\tfor (int i = 0; i < nums.length; i++) {\n\t\t\t\tint min = nums[size];\n\t\t\t\tint minIndex = size;\n\t\t\t\tfor (int j = nums.length - 1; j > size; j--) {\n\t\t\t\t\tif (nums[j] < min) {\n\t\t\t\t\t\tmin = nums[j];\n\t\t\t\t\t\tminIndex = j;\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t\tres[size] = min;\n\t\t\t\tswap(nums, minIndex, size);\n\t\t\t\tsize++;\n\t\t\t}\n\t\t\treturn res;\n\t\t}\n\n\t\tprivate void swap(int[] nums, int i, int j) {\n\t\t\tnums[i] = nums[i] ^ nums[j];\n\t\t\tnums[j] = nums[i] ^ nums[j];\n\t\t\tnums[i] = nums[i] ^ nums[j];\n\t\t}\n\n\t}\n```\n\n**5. Heap Sort**\n```\n\tclass Solution {\n\t\tpublic int[] sortArray(int[] nums) {\n\t\t\tif (nums == null || nums.length < 2) {\n\t\t\t\treturn nums;\n\t\t\t}\n\t\t\theapSort(nums);\n\t\t\treturn nums;\n\t\t}\n\n\t\tprivate void heapSort(int[] nums) {\n\t\t\tfor (int i = nums.length / 2; i >= 0; i--) {\n\t\t\t\theapify(nums, i, nums.length - 1);\n\t\t\t}\n\t\t\tfor (int i = 0; i < nums.length; i++) {\n\t\t\t\tswap(nums, 0, nums.length - 1 - i);\n\t\t\t\theapify(nums, 0, nums.length - 2 - i);\n\t\t\t}\n\t\t}\n\n\t\tprivate void heapify(int[] nums, int start, int end) {\n\t\t\twhile (start <= end) {\n\t\t\t\tint l = 2 * start + 1;\n\t\t\t\tint r = 2 * start + 2;\n\t\t\t\tint maxIndex = start;\n\t\t\t\tif (l <= end && nums[l] > nums[maxIndex]) {\n\t\t\t\t\tmaxIndex = l;\n\t\t\t\t}\n\t\t\t\tif (r <= end && nums[r] > nums[maxIndex]) {\n\t\t\t\t\tmaxIndex = r;\n\t\t\t\t}\n\t\t\t\tif (maxIndex == start) {\n\t\t\t\t\treturn;\n\t\t\t\t}\n\t\t\t\tswap(nums, start, maxIndex);\n\t\t\t\tstart = maxIndex;\n\t\t\t}\n\t\t}\n\n\t\tprivate void swap(int[] nums, int i, int j) {\n\t\t\tint tmp = nums[i];\n\t\t\tnums[i] = nums[j];\n\t\t\tnums[j] = tmp;\n\t\t}\n\t}\n```\n
['Sorting', 'Heap (Priority Queue)', 'Merge Sort', 'Java']