leetcode lecture on algorithm interview in Dachang 14. Sorting algorithm
Video Explanation (efficient learning): Click to learn
catalog:
6. Depth first & breadth first
10. Recursion & divide and conquer
Complexity of common sorting algorithms
Results of n^2 divided by nlogn under different data scales
Common sorting algorithms
Algorithm visualization source: http://visualgo.net/
Bubble sort: time complexity O(n^2)
- Compare adjacent elements and swap them if the first is larger than the second
- After one round, you can ensure that the last number is the largest
- The sorting can be completed by executing n-1 rounds
function bubbleSort(arr) {
var len = arr.length;
for (var i = 0; i < len; i++) {
for (var j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j+1]) { //Pairwise comparison of adjacent elements
var temp = arr[j+1]; //Element exchange
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
Select sort: time complexity O(n^2)
- Find the smallest value in the array and put it first
- Then find the second smallest value and put it in the second place
- And so on, execute n-1 round
function selectionSort(arr) {
var len = arr.length;
var minIndex, temp;
for (var i = 0; i < len - 1; i++) {
minIndex = i;
for (var j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) { //Find the smallest number
minIndex = j; //Save the index of the smallest number
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
Insert sort: time complexity O(n^2)
- Start with the second number and move forward
- Bigger than it, go to the back
- And so on until the last number
function insertionSort(arr) {
var len = arr.length;
var preIndex, current;
for (var i = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i];
while(preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = current;
}
return arr;
}
Merge and sort: time complexity O(nlogn), time complexity O(logn) of division, and complexity O(n) of merging process
-
Divide: divide the array into two halves, recurse the subarray, and perform the division operation until it is divided into a number
-
Combination: combine the two word numbers into an ordered array until all sub arrays are merged. Before merging, prepare an empty array to store the merged results, and then continuously take out the first element of the two sub arrays and compare their sizes. The smaller one first enters the empty array prepared before, and then continues to traverse other elements, Until the elements in the subarray are traversed
function mergeSort(arr) { //The top-down recursive method is adopted
var len = arr.length;
if(len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right)
{
var result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}
Quick sort: time complexity O(nlogn), recursive complexity O(logn), partition complexity O(n)
- Partition: select a benchmark value from the array. The one smaller than the benchmark value is placed in front of it and the one larger than the benchmark value is placed behind it
- Recursion: recursively perform the first step of operation on the subarray before and after the benchmark value
function quickSort(arr, left, right) {
var len = arr.length,
partitionIndex,
left = typeof left != 'number' ? 0 : left,
right = typeof right != 'number' ? len - 1 : right;
if (left < right) {
partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex-1);
quickSort(arr, partitionIndex+1, right);
}
return arr;
}
function partition(arr, left ,right) { //Partition operation
//Of course, you can also select the rightmost element as the benchmark, or you can select it randomly and exchange it with the leftmost or rightmost element
var pivot = left,
index = pivot + 1;
for (var i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index-1;
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
215. The kth largest element in the array (medium)
Method 1. Maintain the small top heap with the size of K. when the number of elements in the heap is less than or equal to K, traverse the array and make the elements of the array continuously add to the heap. When the size of the heap is greater than k, make the elements at the top of the heap out of the column. After traversing the array, the element at the top of the small top heap is the k-largest element.
Complexity: time complexity O(nlogk), n cycles, and each heap operation is O(logk). Spatial complexity O(k),
js:
class Heap {
constructor(comparator = (a, b) => a - b, data = []) {
this.data = data;
this.comparator = comparator;//comparator
this.heapify();//Heap
}
heapify() {
if (this.size() < 2) return;
for (let i = Math.floor(this.size() / 2) - 1; i >= 0; i--) {
this.bubbleDown(i);//bubbleDown operation
}
}
peek() {
if (this.size() === 0) return null;
return this.data[0];//View the top of the heap
}
offer(value) {
this.data.push(value);//Add array
this.bubbleUp(this.size() - 1);//Adjust the position of the added elements in the small top heap
}
poll() {
if (this.size() === 0) {
return null;
}
const result = this.data[0];
const last = this.data.pop();
if (this.size() !== 0) {
this.data[0] = last;//Swap the first and last elements
this.bubbleDown(0);//bubbleDown operation
}
return result;
}
bubbleUp(index) {
while (index > 0) {
const parentIndex = (index - 1) >> 1;//Location of parent node
//If the current element is smaller than the element of the parent node, the positions of the current node and the parent node are exchanged
if (this.comparator(this.data[index], this.data[parentIndex]) < 0) {
this.swap(index, parentIndex);//Swap the location of yourself and the parent node
index = parentIndex;//Continuously take up the parent node for comparison
} else {
break;//If the current element is larger than the element of the parent node, it does not need to be processed
}
}
}
bubbleDown(index) {
const lastIndex = this.size() - 1;//Location of the last node
while (true) {
const leftIndex = index * 2 + 1;//Location of left node
const rightIndex = index * 2 + 2;//Location of the right node
let findIndex = index;//Location of the bubbleDown node
//Find the node with small value in the left and right nodes
if (
leftIndex <= lastIndex &&
this.comparator(this.data[leftIndex], this.data[findIndex]) < 0
) {
findIndex = leftIndex;
}
if (
rightIndex <= lastIndex &&
this.comparator(this.data[rightIndex], this.data[findIndex]) < 0
) {
findIndex = rightIndex;
}
if (index !== findIndex) {
this.swap(index, findIndex);//Swap the current element and the small value in the left and right nodes
index = findIndex;
} else {
break;
}
}
}
swap(index1, index2) {//Swap the positions of the two elements in the heap
[this.data[index1], this.data[index2]] = [this.data[index2], this.data[index1]];
}
size() {
return this.data.length;
}
}
var findKthLargest = function (nums, k) {
const h = new Heap((a, b) => a - b);
for (const num of nums) {
h.offer(num);//Add heap
if (h.size() > k) {//When the size of the heap exceeds k, it is out of the heap
h.poll();
}
}
return h.peek();
};
Method 2: heap sort
- Idea: using the idea of in-situ heap sorting, add the top k-1 element to the tail of the team, and the last top element is the k-largest element
- Complexity: time complexity O(nlogn), heap creation complexity O(n), elements with large k-1 before moving, then heap complexity O(klogn), K < = n, worst case O(nlogn), space complexity O(logn), recursive stack space
js:
var findKthLargest = function (nums, k) {
let heapSize = nums.length;
buildMaxHeap(nums, heapSize); //Build a large top heap with the size of heapSize
//The first k-1 top elements of the large top heap are constantly exchanged with the end elements of the array, and then heapify the top elements again
//This operation is the previous operation of small top stacking out of the top of the heap, but now it is sorted in place
for (let i = nums.length - 1; i >= nums.length - k + 1; i--) {
swap(nums, 0, i);//Swap heap top and array end elements
--heapSize; //Heap size minus 1
maxHeapify(nums, 0, heapSize);//Re heapify
}
return nums[0];//Returns the top element of the heap, which is the k-th largest element
function buildMaxHeap(nums, heapSize) {
for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {//Build from the first non leaf node
maxHeapify(nums, i, heapSize);
}
}
// Adjust the node from left to right and from top to bottom
function maxHeapify(nums, i, heapSize) {
let l = i * 2 + 1;//Left node
let r = i * 2 + 2;//Right node
let largest = i;
if (l < heapSize && nums[l] > nums[largest]) {
largest = l;
}
if (r < heapSize && nums[r] > nums[largest]) {
largest = r;
}
if (largest !== i) {
swap(nums, i, largest); //Find the large element exchange in the left and right nodes
//Recursively swap subsequent nodes
maxHeapify(nums, largest, heapSize);
}
}
function swap(a, i, j) {//Exchange function
let temp = a[i];
a[i] = a[j];
a[j] = temp;
}
};
java:
class Solution {
public int findKthLargest(int[] nums, int k) {
int heapSize = nums.length;
buildMaxHeap(nums, heapSize);
for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
swap(nums, 0, i);
--heapSize;
maxHeapify(nums, 0, heapSize);
}
return nums[0];
}
public void buildMaxHeap(int[] a, int heapSize) {
for (int i = heapSize / 2; i >= 0; --i) {
maxHeapify(a, i, heapSize);
}
}
public void maxHeapify(int[] a, int i, int heapSize) {
int l = i * 2 + 1, r = i * 2 + 2, largest = i;
if (l < heapSize && a[l] > a[largest]) {
largest = l;
}
if (r < heapSize && a[r] > a[largest]) {
largest = r;
}
if (largest != i) {
swap(a, i, largest);
maxHeapify(a, largest, heapSize);
}
}
public void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
Method 3: partition method of quick sort
-
Idea: learn from the idea of fast scheduling and constantly randomly select the benchmark element to see whether the element is in the n-k position after partition.
-
Complexity:
-
Time complexity O(nlogn)
-
Spatial complexity O(logn), depth of recursion
-
js:
const findKthLargest = (nums, k) => {
const n = nums.length;
const quick = (l, r) => {
if (l > r) return;//Recursive termination condition
let random = Math.floor(Math.random() * (r - l + 1)) + l; //Randomly select an index
swap(nums, random, r); //Swap it with the element at position r, with num [r] as the reference element
//partition the base element
let pivotIndex = partition(nums, l, r);
//After partition, the elements on the left of the reference element are smaller than it, and the elements on the right are larger than it
//If the position pivotIndex of the benchmark element after the partition is exactly n-k, the k-th largest number is found
//If n-k < pivotIndex, search recursively on the left of pivotIndex
//If n-k > pivotIndex, recursively search on the right side of pivotIndex
if (n - k < pivotIndex) {
quick(l, pivotIndex - 1);
} else {
quick(pivotIndex + 1, r);
}
};
quick(0, n - 1);//left=0, right= n - 1 passed in at the beginning of the function
return nums[n - k]; //Finally, the correct position is found, that is, n-k is equal to pivotIndex, and the element in this position is the k-th largest number
};
function partition(nums, left, right) {
let pivot = nums[right]; //The rightmost element is the benchmark
let pivotIndex = left; //pivotIndex is initialized to left
for (let i = left; i < right; i++) { //Traverse elements from left to right-1
if (nums[i] < pivot) { //If the current element is smaller than the base element
swap(nums, i, pivotIndex); //Swap it to the location of pivotIndex
pivotIndex++; //pivotIndex moves forward one step
}
}
swap(nums, right, pivotIndex); //Finally, exchange pivotIndex and right
return pivotIndex; //Return pivotIndex
}
function swap(nums, p, q) {//Swap two elements in an array
const temp = nums[p];
nums[p] = nums[q];
nums[q] = temp;
}
java:
class Solution {
Random random = new Random();
public int findKthLargest(int[] nums, int k) {
return quickSelect(nums, 0, nums.length - 1, nums.length - k);
}
public int quickSelect(int[] a, int l, int r, int index) {
int q = randomPartition(a, l, r);
if (q == index) {
return a[q];
} else {
return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index);
}
}
public int randomPartition(int[] a, int l, int r) {
int i = random.nextInt(r - l + 1) + l;
swap(a, i, r);
return partition(a, l, r);
}
public int partition(int[] a, int l, int r) {
int x = a[r], i = l - 1;
for (int j = l; j < r; ++j) {
if (a[j] <= x) {
swap(a, ++i, j);
}
}
swap(a, i + 1, r);
return i + 1;
}
public void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
148. Sorting linked list(medium)
The animation is too large. Click to view it
Method 1: top down
- Idea: use the idea of merging and sorting. First, keep dividing, know that each sub interval has only one node position, and then start merging.
- Complexity: the time complexity O(nlogn) is the same as that of merge sorting. Space complexity O(logn), recursive stack space
js:
const merge = (head1, head2) => {
const dummyHead = new ListNode(0);
let temp = dummyHead, temp1 = head1, temp2 = head2;
while (temp1 !== null && temp2 !== null) {//Merge nodes with small sub interval and connect them first
if (temp1.val <= temp2.val) {
temp.next = temp1;
temp1 = temp1.next;
} else {
temp.next = temp2;
temp2 = temp2.next;
}
temp = temp.next;
}
if (temp1 !== null) {//The nodes of the two linked lists have not been merged, so they can be merged directly
temp.next = temp1;
} else if (temp2 !== null) {
temp.next = temp2;
}
return dummyHead.next;
}
const toSortList = (head, tail) => {
if (head === null) {//Extreme situation
return head;
}
if (head.next === tail) {//Split to only one node
head.next = null;
return head;
}
let slow = head, fast = head;
while (fast !== tail) {//To intermediate node
slow = slow.next;
fast = fast.next;
if (fast !== tail) {
fast = fast.next;
}
}
const mid = slow;
return merge(toSortList(head, mid), toSortList(mid, tail));//Partition interval recursive merging
}
var sortList = function(head) {
return toSortList(head, null);
};
java:
class Solution {
public ListNode sortList(ListNode head) {
return toSortList(head, null);
}
public ListNode toSortList(ListNode head, ListNode tail) {
if (head == null) {
return head;
}
if (head.next == tail) {
head.next = null;
return head;
}
ListNode slow = head, fast = head;
while (fast != tail) {
slow = slow.next;
fast = fast.next;
if (fast != tail) {
fast = fast.next;
}
}
ListNode mid = slow;
ListNode list1 = toSortList(head, mid);
ListNode list2 = toSortList(mid, tail);
ListNode sorted = merge(list1, list2);
return sorted;
}
public ListNode merge(ListNode head1, ListNode head2) {
ListNode dummyHead = new ListNode(0);
ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
while (temp1 != null && temp2 != null) {
if (temp1.val <= temp2.val) {
temp.next = temp1;
temp1 = temp1.next;
} else {
temp.next = temp2;
temp2 = temp2.next;
}
temp = temp.next;
}
if (temp1 != null) {
temp.next = temp1;
} else if (temp2 != null) {
temp.next = temp2;
}
return dummyHead.next;
}
}
Method 2: bottom up
- Idea: directly carry out circular merging operation.
- Complexity: time complexity O(nlogn), space complexity O(1)
js:
const merge = (head1, head2) => {
const dummyHead = new ListNode(0);
let temp = dummyHead, temp1 = head1, temp2 = head2;
while (temp1 !== null && temp2 !== null) {
if (temp1.val <= temp2.val) {
temp.next = temp1;
temp1 = temp1.next;
} else {
temp.next = temp2;
temp2 = temp2.next;
}
temp = temp.next;
}
if (temp1 !== null) {
temp.next = temp1;
} else if (temp2 !== null) {
temp.next = temp2;
}
return dummyHead.next;
}
var sortList = function(head) {
if (head === null) {
return head;
}
let length = 0;
let node = head;
while (node !== null) {
length++;
node = node.next;
}
const dummyHead = new ListNode(0, head);
for (let subLength = 1; subLength < length; subLength <<= 1) {
let prev = dummyHead, curr = dummyHead.next;
while (curr !== null) {
let head1 = curr;
for (let i = 1; i < subLength && curr.next !== null; i++) {
curr = curr.next;
}
let head2 = curr.next;
curr.next = null;
curr = head2;
for (let i = 1; i < subLength && curr != null && curr.next !== null; i++) {
curr = curr.next;
}
let next = null;
if (curr !== null) {
next = curr.next;
curr.next = null;
}
const merged = merge(head1, head2);
prev.next = merged;
while (prev.next !== null) {
prev = prev.next;
}
curr = next;
}
}
return dummyHead.next;
};
java:
class Solution {
public ListNode sortList(ListNode head) {
if (head == null) {
return head;
}
int length = 0;
ListNode node = head;
while (node != null) {
length++;
node = node.next;
}
ListNode dummyHead = new ListNode(0, head);
for (int subLength = 1; subLength < length; subLength <<= 1) {
ListNode prev = dummyHead, curr = dummyHead.next;
while (curr != null) {
ListNode head1 = curr;
for (int i = 1; i < subLength && curr.next != null; i++) {
curr = curr.next;
}
ListNode head2 = curr.next;
curr.next = null;
curr = head2;
for (int i = 1; i < subLength && curr != null && curr.next != null; i++) {
curr = curr.next;
}
ListNode next = null;
if (curr != null) {
next = curr.next;
curr.next = null;
}
ListNode merged = merge(head1, head2);
prev.next = merged;
while (prev.next != null) {
prev = prev.next;
}
curr = next;
}
}
return dummyHead.next;
}
public ListNode merge(ListNode head1, ListNode head2) {
ListNode dummyHead = new ListNode(0);
ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
while (temp1 != null && temp2 != null) {
if (temp1.val <= temp2.val) {
temp.next = temp1;
temp1 = temp1.next;
} else {
temp.next = temp2;
temp2 = temp2.next;
}
temp = temp.next;
}
if (temp1 != null) {
temp.next = temp1;
} else if (temp2 != null) {
temp.next = temp2;
}
return dummyHead.next;
}
}