【 method 】 (bubble | | fast merge sort

directory

0. Sorting classification
1. Swap sort – Bubble sort
2. Swap sort – Quicksort
3. Merge sort
4. Quicksort and merge
5. Ten basic sorts

Zero, sort classification

Swap sort – bubble sort

Compare adjacent elements in pairs. When one element is larger than the one on the right, swap them. When one element is less than or equal to its neighbor on the right, the position doesn’t change

function bubbleSort(list:Array<number>) {
    < length-1 = < length-1
    for (let i = 0; i < list.length - 1; i++) {
        // The reason why < length-1 is the same as the reason why -i is the ordered region
        for (let j = 0; j < list.length - i -1; j++) {
            if( list[j] > list[j+1]) {
                let temp = list[j];
                list[j] = list[j+1];
                list[j+1] = temp


            }
        }
    }
    return list
}

Copy the code

1.1) Bubble sorting optimization

** Improved bubble sort: ** Set a token variable pos, which records the position of the last swap in each sort run. Since all the records after the POS position have been swapped in place, it is only necessary to scan the POS position in the next sorting.

// Whether the ordered identifier is optimized
function bubbleSortTwo(list: Array<number>) {
    < length-1 = < length-1
    for (let i = 0; i < list.length - 1; i++) {
        let isSorted = true; // Order each round to be true
        for (let j = 0; j < list.length - i - 1; j++) {
            if (list[j] > list[j + 1]) {
                let temp = list[j];
                list[j] = list[j + 1];
                list[j + 1] = temp;
                // If an exchange occurs, it is not ordered
                isSorted = false; }}if (isSorted) {
            break; }}return list;
}

Copy the code

function bubbleSort2(arr) {
    console.time('Improved bubble sort time');
    var i = arr.length-1;  // At the beginning, the last position remains the same
    while ( i> 0) {
        var pos= 0; // At the start of each run, no record is exchanged
        for (var j= 0; j< i; j++)
            if (arr[j]> arr[j+1]) {
                pos= j; // Record the location of the swap
                var tmp = arr[j]; arr[j]=arr[j+1]; arr[j+1]=tmp;
            }
        i= pos; // Get ready for the next sort
     }
     console.timeEnd('Improved bubble sort time');
     return arr;
}
var arr=[3.44.38.5.47.15.36.26.27.2.46.4.19.50.48];
console.log(bubbleSort2(arr));/ / [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

Copy the code

1.2) Bubble sort performance analysis

Elements of the same size do not swap places, so bubble sort is stable.

Two, exchange sort –Quick sort

The idea is to find the smallest or largest element in the unsorted sequence, place it at the beginning of the sorted sequence, then relay the smallest or largest element to the unsorted sequence, and place it at the end of the sorted sequence. And so on until all the elements are sorted.

Consider an example of sorting an array by selection [2,5,4,1,3].

• First, find the smallest element in the array, 1, and swap it with the first element in the array

• On the second trip, find the smallest element in the unsorted array, 2, and swap places with the second element in the array.

Selection sort 2

• On the third trip, find the smallest element in the unsorted array, 3, and swap places with the third element in the array.

Select sort -3

• On the fourth trip, find the smallest element in the unsorted array, 4, and swap places with the fourth element in the array.

Selection sort 4

So at this point, our array is sorted.

Selection sort 5

2.1) Select the sorting code implementation

The idea of choosing sort is very simple and not difficult to implement.

const quickSort1 = arr= > {
	if (arr.length <= 1) {
		return arr;
	}
	// select a reference point
	const midIndex = Math.floor(arr.length / 2);
	// Splice (index,1) returns an array of deleted elements.
	const valArr = arr.splice(midIndex, 1);
	const midIndexVal = valArr[0];
	const left = []; // Store an array smaller than the datum
	const right = []; // Store an array larger than the datum
	// Run the following command through the array
	for (let i = 0; i < arr.length; i++) {
		if (arr[i] < midIndexVal) {
			left.push(arr[i]); // Those smaller than the reference point are placed in the left array
		} else {
			right.push(arr[i]); // Those larger than the datum are placed in the right array}}// Do this recursively, operating on the left and right arrays until the array length is <= 1
	return quickSort1(left).concat(midIndexVal, quickSort1(right));
};
const array2 = [5.4.3.2.1];
console.log('quickSort1 ', quickSort1(array2));
// quickSort1: [1, 2, 3, 4, 5]


Copy the code

2.2) Selection sorting performance analysis

Is selection sort stable?

The answer is unstable because the minimum value found in the unsorted sequence is swapped with the last element of the sorted sequence.

Quicksort is fast and efficient! It is one of the fastest sorting algorithms for big data.

thought

• First find a reference point (the middle of the general index group), then the array is divided into two parts by that reference point, compare the reference point data, if smaller than it, put to the left; Instead, put it on the right.
• An empty array is used to store the comparison data.
• We recurse until the array length <= 1;

Features: Fast, often used.

Disadvantages: Need to declare two additional arrays, waste memory space resources.

Merge sort

thought

To sort an array, we divide the array into two parts, sort the two parts separately, and merge the sorted parts together so that the entire array is sorted.

Merge sort is divide-and-conquer.

Divide and conquer, as the name suggests, is to divide and conquer, to solve a big problem by breaking it down into smaller sub-problems. When small sub-problems are solved, big problems are solved.

Quicksort and merge

Quicksort and merge are divide-and-conquer, and recursive formulas and recursive code are very similar, so what’s the difference?

It can be found:

• So what merge sort does isFrom bottom upFirst deal with subproblems and then merge.
• Quicksort, on the other hand, does the same thingtop-downPartition first and then deal with sub-problems.
• Although merge sort is a stable sorting algorithm with O(nlogn) time complexity, it is a non-in-situ sorting algorithm.
• The main reason why merge is a non-in-place sort algorithm is that the merge function cannot be executed in place.
• Quicksort can realize in-place sort by cleverly designed in-place partition function, which solves the problem that merge sort occupies too much memory.

reference

• 666- Ten sorted JAVA versions
• www.sohu.com/a/249036484…
• 666- Ten sorted JS versions

conclusion

1. Sorting is divided into: comparison sort and non-comparison sort
2. Compare adjacent elements in pairs. When one element is larger than the one on the right, swap them. When one element is less than or equal to its neighbor on the right, the position doesn’t change
3. Merge sort is going to beDivide and conquer thoughts.Divide and rule, as the name suggests, means divide and ruleTo solve a big problem by breaking it into smaller sub-problems. When small sub-problems are solved, big problems are solved.

to-do

• Data structure and algorithm learning guide

• The path of algorithm learning

• The sorting