<> Ten classic sorting algorithms
Today, sort out the top ten classic sorting algorithms .
<>1, Bubble sorting
—— The smaller elements will be exchanged slowly “ float ” To the top of the sequence
<> Algorithm demonstration
<> Algorithm steps
* Compare adjacent elements . If the first is bigger than the second , Just exchange them two ;
* Do the same for each pair of adjacent elements , The first pair from the beginning to the last pair at the end , In this way, the last element should be the maximum number ;
* Repeat the above steps for all elements , Except the last one ;
* Repeat step 1~3, Until sorting is complete .
<> Algorithm implementation
def bubbleSort(arr): for i in range(1, len(arr)): for j in range(0, len(arr)-i)
: if arr[j] > arr[j+1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] return arr
<>2, Select sort
—— The smallest comes out first , The second youngest came out second …
<> Algorithm demonstration
<> Algorithm steps
* First, find the smallest in the unordered sequence （ large ） element , Stored at the beginning of the sort sequence .
* Then continue to find the smallest from the remaining unordered elements （ large ） element , Then put it at the end of the sorted sequence .
* Repeat step 2 , Until all elements are sorted .
<> Algorithm implementation
def selectionSort(arr): for i in range(len(arr) - 1): # Record the index of the smallest number minIndex = i
for j in range(i + 1, len(arr)): if arr[j] < arr[minIndex]: minIndex = j # i
When not the minimum , take i Exchange with the lowest decimal if i != minIndex: arr[i], arr[minIndex] = arr[minIndex], arr
[i] return arr
<>3, Simple insert sort
—— By constructing an ordered sequence , For unsorted data , Scan back and forward in sorted sequence , Locate and insert .
<> Algorithm demonstration
<> Algorithm steps
* Start with the first element , The element can be considered to have been sorted ;
* Take out the next element , Scan back and forward in the sorted element sequence ;
* If this element （ Sorted ） Greater than new element , Move the element to the next position ;
* Repeat step 3, Until the sorted element is found to be less than or equal to the position of the new element ;
* After inserting the new element into this location ;
* Repeat step 2~5.
<> Algorithm implementation
def insertionSort(arr): for i in range(len(arr)): preIndex = i-1 current = arr[
i] while preIndex >= 0 and arr[preIndex] > current: arr[preIndex+1] = arr[
preIndex] preIndex-=1 arr[preIndex+1] = current return arr
<>4, Shell Sort
—— Shell Sort , Also known as decreasing incremental sorting algorithm , Is a more efficient and improved version of insert sorting .
<> Algorithm demonstration
<> Algorithm steps
* Select an incremental sequence t1,t2,……,tk, among ti > tj, tk = 1;
* Number of sequence by increment k, Sequence k Trip sort ;
* Sort per trip , According to the corresponding increment ti, The sequence to be arranged is divided into several lengths m Subsequence of , Insert and sort each sub table directly . Only increment factor is 1
Time , The entire sequence is treated as a table , The table length is the length of the entire sequence .
<> Algorithm implementation
def shellSort(arr): import math gap=1 while(gap < len(arr)/3): gap = gap*3+1
while gap > 0: for i in range(gap,len(arr)): temp = arr[i] j = i-gap while j >=0
and arr[j] > temp: arr[j+gap]=arr[j] j-=gap arr[j+gap] = temp gap = math.floor(
gap/3) return arr
<>5, Merge sort
—— An effective sorting algorithm based on merging operation . The algorithm adopts divide and conquer method （Divide and Conquer） A very typical application of .
<> Algorithm demonstration
<> Algorithm steps
* Application space , Make it the sum of two sorted sequences , This space is used to store the merged sequence ;
* Set two pointers , The initial position is the starting position of the two sorted sequences ;
* Compare the elements pointed to by two pointers , Select a relatively small element to put into the merge space , And move the pointer to the next position ;
* Repeat step 3 Until a pointer reaches the end of the sequence ;
* Copy all the remaining elements of another sequence directly to the end of the merged sequence .
<> Algorithm implementation
def mergeSort(arr): import math if(len(arr)<2): return arr middle = math.floor(
len(arr)/2) left, right = arr[0:middle], arr[middle:] return merge(mergeSort(
left), mergeSort(right)) def merge(left,right): result = [] while left and right
: if left[0] <= right[0]: result.append(left.pop(0)) else: result.append(right.
pop(0)); while left: result.append(left.pop(0)) while right: result.append(right
.pop(0)); return result
<>6, Quick sort
—— Quick sort uses divide and conquer （Divide and conquer） Strategy to put a serial （list） It is divided into two subseries （sub-lists）.
Quick sorting is a typical application of divide and conquer in sorting algorithm . In essence , Quick sort should be a recursive divide and conquer method based on bubble sort .
<> Algorithm demonstration
<> Algorithm steps
* Pick an element from the sequence , be called “ benchmark ”（pivot）;
*
Reorder sequence , All elements smaller than the datum value are placed in front of the datum , All elements larger than the datum value are placed behind the datum （ The same number can go to either side ）. After this partition exits , The benchmark is in the middle of the sequence . This is called a partition （partition） operation ;
* Recursively （recursive） Sort the subsequence of the element less than the reference value and the subsequence of the element greater than the reference value ;
<> Algorithm implementation
def quickSort(arr, left=None, right=None): left = 0 if not isinstance(left,(int
, float)) else left right = len(arr)-1 if not isinstance(right,(int, float))
else right if left < right: partitionIndex = partition(arr, left, right)
quickSort(arr, left, partitionIndex-1) quickSort(arr, partitionIndex+1, right)
return arr def partition(arr, left, right): pivot = left index = pivot+1 i =
indexwhile i <= right: if arr[i] < arr[pivot]: swap(arr, i, index) index+=1 i+=1
swap(arr,pivot,index-1) return index-1 def swap(arr, i, j): arr[i], arr[j] =
arr[j], arr[i]
<>7, Heap sort
—— A sort algorithm designed by using heap data structure
<> Algorithm demonstration
<> Algorithm steps
* Create a heap H[0……n-1];
* Put the pile head （ Maximum ） And tail interchange ;
* Reduce the size of the pile 1, And call shift_down(0), The purpose is to adjust the top data of the new array to the corresponding position ;
* Repeat step 2, Until the size of the stack is 1.
<> Algorithm implementation
def buildMaxHeap(arr): import math for i in range(math.floor(len(arr)/2),-1,-1)
: heapify(arr,i) def heapify(arr, i): left = 2*i+1 right = 2*i+2 largest = i if
left< arrLen and arr[left] > arr[largest]: largest = left if right < arrLen and
arr[right] > arr[largest]: largest = right if largest != i: swap(arr, i, largest
) heapify(arr, largest) def swap(arr, i, j): arr[i], arr[j] = arr[j], arr[i] def
heapSort(arr): global arrLen arrLen = len(arr) buildMaxHeap(arr) for i in range(
len(arr)-1,0,-1): swap(arr,0,i) arrLen -=1 heapify(arr, 0) return arr
<>8, Count sort
—— As a sort of linear time complexity , Count sorting requires that the input data must be an integer with a definite range .
<> Algorithm demonstration
<> Algorithm steps
* Find the largest and smallest elements in the array to be sorted
* Each value in the statistics array is i The number of occurrences of the element , Save to array C The first i term
* All counts are accumulated （ from C Start with the first element in , Each item is added to the previous one ）
* Reverse fill target array ： Put each element i Put in the second row of the new array C(i) term , Every time you put an element C(i) subtract 1
<> Algorithm implementation
def countingSort(arr, maxValue): bucketLen = maxValue+1 bucket = [0]*bucketLen
sortedIndex=0 arrLen = len(arr) for i in range(arrLen): if not bucket[arr[i]]:
bucket[arr[i]]=0 bucket[arr[i]]+=1 for j in range(bucketLen): while bucket[j]>0:
arr[sortedIndex] = j sortedIndex+=1 bucket[j]-=1 return arr
<>9, Bucket sorting
—— Bucket sorting is an upgraded version of counting sorting . It uses the mapping relationship of functions , The key to high efficiency lies in the determination of the mapping function .
<> Algorithm demonstration
[ External chain picture transfer failed , The origin station may have anti-theft chain mechanism , It is recommended to save the picture and upload it directly (img-9ybEGKPU-1633970885002)(C:\Users\LANWEI~1\AppData\Local\Temp\1633970398356.png)]
<> Algorithm steps
* Set a quantitative array as an empty bucket ;
* Traverse input data , And put the data into the corresponding bucket one by one ;
* Sort each bucket that is not empty ;
* Splice the ordered data from a bucket that is not empty .
<> Algorithm implementation
function bucketSort(arr, bucketSize) { if (arr.length === 0) { return arr; }
var i; var minValue = arr[0]; var maxValue = arr[0]; for (i = 1; i < arr.length;
i++) { if (arr[i] < minValue) { minValue = arr[i]; // Minimum value of input data } else if (arr[i
] > maxValue) { maxValue = arr[i]; // Maximum value of input data } } // Initialization of bucket var
DEFAULT_BUCKET_SIZE= 5; // Set the default number of buckets to 5 bucketSize = bucketSize ||
DEFAULT_BUCKET_SIZE; var bucketCount = Math.floor((maxValue - minValue) /
bucketSize) + 1; var buckets = new Array(bucketCount); for (i = 0; i < buckets.
length; i++) { buckets[i] = []; } // The mapping function is used to allocate the data to each bucket for (i = 0; i < arr.length
; i++) { buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]); }
arr.length = 0; for (i = 0; i < buckets.length; i++) { insertionSort(buckets[i])
; // Sort each bucket , Insert sort is used here for (var j = 0; j < buckets[i].length; j++) { arr.push(
buckets[i][j]); } } return arr; }
<>10, Cardinality sort
Cardinality sorting is sorting by low order first , Then collect ; Then sort by high order , Then collect ; And so on , Up to the top . Sometimes some attributes are prioritized , Sort by low priority first , Then sort by high priority . The last order is high priority, high priority first , The high priority is the same as the low priority, and the high priority is the first .
<> Algorithm demonstration
<> Algorithm steps
* Gets the maximum number of in the array , And get the number of digits ;
* arr Is the original array , Each bit is taken from the lowest bit radix array ;
* yes radix Sort by count （ Using the characteristics that counting sorting is suitable for a small range of numbers ）;
<> Algorithm implementation
var counter = []; function radixSort(arr, maxDigit) { var mod = 10; var dev = 1
; for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) { for(var j = 0; j <
arr.length; j++) { var bucket = parseInt((arr[j] % mod) / dev); if(counter[
bucket]==null) { counter[bucket] = []; } counter[bucket].push(arr[j]); } var pos
= 0; for(var j = 0; j < counter.length; j++) { var value = null; if(counter[j]!=
null) { while ((value = counter[j].shift()) != null) { arr[pos++] = value; } } }
} return arr; }
Technology