“This is the second day of my participation in the November Gwen Challenge. See details of the event: The last Gwen Challenge 2021”.
Sorting algorithm stability and sorting algorithm classification
Stability of sorting algorithm: it can guarantee two equal values, their relative position is unchanged before sorting, that is, A [0]=3, A [5]=3, if the sorting can ensure that the 3 of a[0] in front of the 3 of a[5] is a stable algorithm;
Common sorting algorithms fall into the following categories:
Graph of TD a sorting algorithm (common) -- - > b (exchange) a - > b1 (selection) a - - > b2 (insertion sort) -- > b3 (merge sort) b - bubble sort () - > b > c c1 (quick sort) b1 - > c2 (selection) B1 --> c3(heap sort) b2 --> C4 (insert sort) B2 --> C5 (Hill sort)Exchange sort
Bubble sort algorithm idea
Bubbling sort, as its name suggests, bubbles slowly to the surface of the water; Bubble sort where each number is like a bubble, and the way the bubble rises to the surface of the water is bubble sort comparison, bubble sort is by comparing two adjacent numbers, if a> B or B > A, they switch positions until they come to the surface.
Bubble sort 1
func Sbubble1(ans []int) {
ansLen := len(ans)
for i := 0; i < ansLen; i++ {
for j := 0; j < ansLen- 1-i; j++ {
if ans[j] > ans[j+1] {
ans[j], ans[j+1] = ans[j+1], ans[j]
}
}
}
fmt.Printf("Bubble sort: %d random numbers \n", ansLen)
}
Copy the codeBubble sort 2
Bubble sort is optimized for bubble sort by adding a local variable to record whether or not bubble sort swaps each round. If there is no swap, then all the numbers are already in order, and there is no need to compare them and terminate the loop.
func Sbubble2(ans []int) {
ansLen := len(ans)
flag := true
for i := 0; i < ansLen && flag; i++ {
flag = false
for j := 0; j < ansLen- 1-i; j++ {
if ans[j] > ans[j+1] {
ans[j], ans[j+1] = ans[j+1], ans[j]
flag = true
//ExportArray(&ans)
}
}
}
fmt.Printf("Bubble sort: %d random numbers \n", ansLen)
}
Copy the codeQuick sort
So the idea of quicksort is very simple, you take a hub, you put anything larger than it on the right, anything smaller than it on the left, and then you use divide-and-conquer, keep dividing, and finally sort
func QuickSort(ans []int, low, high int) {
if low < high {
pivot := partition(ans, low, high)
QuickSort(ans, low, pivot- 1)
QuickSort(ans, pivot+1, high)
}
}
func partition(ans []int, low, high int) int {
pivot := ans[low]
for low < high {
for ; low < high && ans[high] >= pivot; high-- {
}
ans[low] = ans[high]
for ; low < high && ans[low] <= pivot; low++ {
}
ans[high] = ans[low]
}
ans[low] = pivot
return low
}
Copy the codeSelection sort
Algorithm thought
Selection sorting, its core is the selection process, the selection process is to choose the maximum or minimum number, if it is n number, it is necessary to carry out n-1 round of comparison, and finally achieve the sorting process; The exact process is to start with the ith number, and then the ith +1… N minus one numbers, find the largest or smallest number, and then switch places with the ith number
Selection sort
func Selection(ans []int) {
ansLen := len(ans)
for i := 0; i < ansLen- 1; i++ {
minpos := i
for j := i + 1; j < ansLen; j++ {
if ans[j] < ans[minpos] {
minpos = j
}
}
ifminpos ! = i { ans[minpos], ans[i] = ans[i], ans[minpos] } } }Copy the codeHeap sort
Heap sort, in fact, is a complete binary tree, the heap is divided into big top heap, where each node is greater than or equal to every node of its child tree, and small top heap, where each node of its child tree is less than or equal to every node of its child tree. The process of heap sorting is also the process of adjustment. The maximum or minimum value can be adjusted through adjustment again and again, and the ordered sequence can be finally adjusted through n-1 adjustment. First of all, the adjustment is to start from the last non-leaf node and compare its left and right subtrees. If it is smaller than the subtree, they will be swapped. At this time, the original order may be upset, and the adjustment should continue from the swapped subtree.
func HeapSort(ans []int) {
ansLen := len(ans)
for i := ansLen/2 - 1; i >= 0; i-- {
adjustHeap(ans, i, ansLen)
}
for j := ansLen - 1; j > 0; j-- {
ans[0], ans[j] = ans[j], ans[0]
adjustHeap(ans, 0, j)
}
fmt.Printf("Heap sort: %d random numbers \n", ansLen)
}
func adjustHeap(ans []int, i, length int) {
pos := i
for k := 2*i + 1; k < length; k = 2*k + 1 {
if k+1 < length && ans[k] < ans[k+1] {
k++
}
if ans[k] > ans[pos] {
ans[k], ans[pos] = ans[pos], ans[k]
pos = k
} else {
break}}}Copy the codeInsertion sort
Direct insertion sort
Is sequence is divided into two parts, the left is already ordered, right is unordered, every time take out a number of a disorderly, if be small order, is starting from the orderly sequence of the last more than a big, if you and a exchange, on a continued and it’s a number, until you find a smaller number. Then we continue to take numbers from the unordered sequence, and repeat until we have all the unordered sequences, and we’re done sorting.
func Sinsert(ans []int) {
ansLen := len(ans)
for i := 1; i < ansLen; i++ {
for j := i - 1; j >= 0; j-- {
if ans[j+1] < ans[j] {
ans[j+1], ans[j] = ans[j], ans[j+1]}else {
//ExportArray(&ans)
break
}
}
}
fmt.Printf("Direct insert sort: %d random numbers \n", ansLen)
}
Copy the codeHill sorting
The basic idea of Hill sorting is to divide the whole sequence of records to be sorted into several sub-sequences for direct insertion sorting respectively. When the records in the whole sequence are basically in order, direct insertion sorting is performed for all records
func Shellsort(ans []int) {
ansLen := len(ans)
for increment := ansLen / 2; increment >= 1; increment = increment / 2 {
for i := increment; i < ansLen; i++ {
for j := i - increment; j >= 0 && ans[j] > ans[j+increment]; j -= increment {
ans[j], ans[j+increment] = ans[j+increment], ans[j]
//ExportArray(&ans)
}
}
}
fmt.Printf("Hill sort: %d random numbers \n", ansLen)
}
Copy the codeMerge sort
Merge sort is partition algorithm is one of the most direct, by merging 2 road tell it here, is to divide the sequence into two a group, if more than one directly as a group, each group 2 number comparison sorting, after each subsequence orderly, then the two merged, finally merged into an ordered sequence, completes the order
func MergeSort(ans []int) []int {
ansLen := len(ans)
if ansLen < 2 {
return ans
}
left := ans[0:(ansLen / 2)]
right := ans[(ansLen/2 + 1) :]return merge(MergeSort(left), MergeSort(right))
}
func merge(left []int, right []int) []int {
var res []int
for len(left) ! =0 && len(right) ! =0 {
if left[0] <= right[0] {
res = append(res, left[0])
left = left[1:]}else {
res = append(res, right[0])
right = right[1:]}}for len(left) ! =0 {
res = append(res, left[0])
left = left[1:]}for len(right) ! =0 {
res = append(res, right[0])
right = right[1:]}return res
}
Copy the codeRadix sort
Radix sort, from the ones place, the tens place, the hundreds place… When all the digits are in their buckets, start pulling all the digits out of bucket 0. Then repeat the process for tens, hundreds, and so on until you reach the highest digit. Finally, all the digits are in order
func RadixSort(ans []int) {
length := getMaxNumLen(ans)
mod := 10
for i := 1; i <= length; i++ {
tmp := setBucket(ans, mod)
mod *= 10
getArray(tmp, ans)
}
}
func getMaxNumLen(ans []int) int {
maxNum := ans[0]
for i := 0; i < len(ans); i++ {
if maxNum < ans[i] {
maxNum = ans[i]
}
}
maxStr := strconv.Itoa(maxNum)
return len(maxStr)
}
func setBucket(ans []int, num int)[] []int {
tmp := make([] []int.10000000)
for j := 0; j < len(ans); j++ {
bucketValue := ans[j] % num / (num / 10)
tmp[bucketValue] = append(tmp[bucketValue], ans[j])
}
return tmp
}
func getArray(tmp [][]int, ans []int) {
cnt := 0
for i := 0; i < 10; i++ {
for j := 0; j < len(tmp[i]); j++ {
ans[cnt] = tmp[i][j]
cnt++
}
}
//ExportArray(ans)
}
Copy the code