算法-排序详解[多语言实现]
一.冒泡排序
1.最常见的写法:
最基础的冒泡排序实现
c++:
1 2 3 4 5 6 7 8 9 10
| void bubbleSort(vector<int>& arr) { int length = arr.size(); for (int i = 0;i < length - 1;i++) { for (int j = 0;j < length - 1 - i;j++) { if (arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); } } } }
|
JavaScript:
1 2 3 4 5 6 7 8 9 10
| function bubbleSort(arr) { let length = arr.length for(let i=0;i<length-1;i++) { for(let j=0;j<length-1-i;j++) { if(arr[j]>arr[j+1]){ [arr[j],arr[j+1]] = [arr[j+1],arr[j]] } } } }
|
go:
1 2 3 4 5 6 7 8 9 10
| func bubbleSort(arr []int) { length := len(arr) for i := 0;i<length-1;i++ { for j :=0;j<length-1-i;j++ { if(arr[j]>arr[j+1]) { arr[j],arr[j+1] = arr[j+1],arr[j] } } } }
|
2.优化版:带标志位
通过标志位减少不必要的比较
c++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| void bubbleSort(vector<int>& arr) { int length = arr.size(); bool flag = true; while (length > 1 && flag) { flag = false; for (int i = 0;i < length - 1;i++) { if (arr[i] > arr[i + 1]) { flag = true; swap(arr[i], arr[i + 1]); } } length--; } }
|
JavaScript:
1 2 3 4 5 6 7 8 9 10 11 12 13
| function bubbleSort(arr) { let flag = true let length = arr.length while(length>1&&flag) { flag = false for(let i=0;i<length-1;i++) { if(arr[i]>arr[i+1]){ [arr[i],arr[i+1]] = [arr[i+1],arr[i]] } } length-- } }
|
go:
1 2 3 4 5 6 7 8 9 10 11 12 13
| func bubbleSort(arr []int) { length,flag := len(arr),true for length>1&&flag { flag = false for i := 0;i<length-1;i++ { if(arr[i]>arr[i+1]){ flag = true arr[i],arr[i+1] = arr[i+1],arr[i] } } length-- } }
|
3.双向冒泡排序
从两侧依次冒泡
c++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| void bubbleSort(vector<int>& arr) { int left = 0; int right = arr.size() - 1; bool flag = true; while (right > left && flag) { flag = false; for (int i = left;i < right;i++) { if (arr[i] > arr[i + 1]) { flag = true; swap(arr[i], arr[i + 1]); } } right--; for (int j = right;j > left;j++) { if (arr[j - 1] > arr[j]) { swap(arr[j - 1], arr[j]); } } left++; } }
|
JavaScript:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| function bubbleSort(arr) { let left = 0 let right = arr.length-1 let flag = true while(right>left&&flag) { flag = false for(let i=left;i<right;i++) { if(arr[i]>arr[i+1]){ flag = true [arr[i],arr[i+1]] = [arr[i+1],arr[i]] } } right-- for(let j=right;j>left;j--) { if(arr[j]<arr[j-1]){ flag = true [arr[j],arr[j-1]] = [arr[j-1],arr[j]] } } left++ } }
|
go:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| func bubbleSort(arr []int) { left,right,flag := 0,len(arr)-1,true for right>left&&flag { flag = false for i :=left;i<right;i++ { if(arr[i]>arr[i+1]) { flag = true arr[i],arr[i+1] = arr[i+1],arr[i] } } right-- for j :=right;j>left;j-- { if(arr[j]<arr[j-1]) { flag = true arr[j],arr[j-1] = arr[j-1],arr[j] } } left++ } }
|
4.递归实现
通过递归的方式实现冒泡排序
c++:
1 2 3 4 5
| void bubbleSort(vector<int>& arr,int length) { if (length == 1)return; for (int i = 0;i < length - 1;i++)if (arr[i] > arr[i + 1]) swap(arr[i], arr[i + 1]); return bubbleSort(arr, length - 1); }
|
JavaScript:
1 2 3 4 5
| function bubbleSort(arr,length) { if(length===1)return; for(let i=0;i<length-1;i++)if(arr[i]>arr[i+1]) [arr[i],arr[i+1]] = [arr[i+1],arr[i]] return bubbleSort(arr,length-1) }
|
go:
1 2 3 4 5
| func bubbleSort(arr []int,length int) { if length==1 {return} for i:=0;i<length-1;i++ {if arr[i]>arr[i+1] {arr[i],arr[i+1] = arr[i+1],arr[i]}} bubbleSort(arr,length-1) }
|
二.快速排序
1.最常见的写法:
使用递归实现快速排序,适合初学者理解
c++:
JavaScript:
go:
2.非递归写法(用栈模拟)
通过栈模拟递归逻辑
c++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| void QuickSort(vector<int>& arr) { int length = arr.size(); if (length <= 1)return; stack<pair<int, int>>Boundary; Boundary.push({ 0,length - 1 }); while (!Boundary.empty()) { int left = Boundary.top().first; int right = Boundary.top().second; Boundary.pop(); if (right > left) { int middle = left + (right - left) / 2; int middlenumber = arr[middle]; int leftnumber = left; int rightnumber = right; while (rightnumber >= leftnumber) { while (arr[leftnumber] < middlenumber)leftnumber++; while (arr[rightnumber] > middlenumber)rightnumber--; if (rightnumber >= leftnumber) { swap(arr[rightnumber], arr[leftnumber]); rightnumber--; leftnumber++; } } Boundary.push({ left,rightnumber }); Boundary.push({ leftnumber,right }); } } }
|
JavaScript:
go:
3.原地快速排序(双指针)
在数组中进行原地排序,节省额外空间
在这里我采用从中间位置为基准点(纯属个人习惯)
注:选择数组的中间元素作为基准,避免了选择第一个元素导致最坏情况(已排序数组)的问题。通过使用左右指针(leftnumber
和 rightnumber
),分别从两端向中间扫描,找到不符合条件的元素并交换,直到指针交错。然后递归地对左右子数组进行排序,确保每次划分较为均匀,从而优化了排序性能,特别是在应对已排序或逆序数组时,减少了退化为 O(n2)O(n^2)O(n2) 的风险。
c++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| void QuickSort(vector<int>&arr, int left, int right) { if (left >= right)return; int targetnumber = arr[(left + right) / 2]; int leftnumber = left; int rigthnumber = right; while (rigthnumber >= leftnumber) { while (arr[leftnumber] < targetnumber)leftnumber++; while (arr[rigthnumber] > targetnumber)rigthnumber--; if (rigthnumber > leftnumber) { swap(arr[leftnumber], arr[rigthnumber]); leftnumber++; rigthnumber--; } else if (rigthnumber == leftnumber)break; } if (left < rigthnumber) QuickSort(arr, left, rigthnumber); if (leftnumber < right) QuickSort(arr, leftnumber, right); }
|
JavaScript:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| function QuickSort(arr,left,right) { if(left>=right)return let middlenumber = arr[Math.floor((left + right)/2)] let leftnumber = left let rightnumber = right while(rightnumber >= leftnumber) { while(arr[leftnumber] < middlenumber) leftnumber++ while(arr[rightnumber] > middlenumber) rightnumber-- if(rightnumber >= leftnumber) { [arr[leftnumber],arr[rightnumber]] = [arr[rightnumber],arr[leftnumber]] leftnumber++ rightnumber-- } } QuickSort(arr,left,rightnumber) QuickSort(arr,leftnumber,right) }
|
go:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| func QuickSort(arr []int,left int,right int) { if left>=right {return} middlenumber,leftnumber,rightnumber:=arr[(left+right)/2],left,right for rightnumber >=leftnumber { for arr[leftnumber] < middlenumber {leftnumber++} for arr[rightnumber] >middlenumber {rightnumber--} if rightnumber >= leftnumber { arr[leftnumber],arr[rightnumber] = arr[rightnumber],arr[leftnumber] leftnumber++ rightnumber-- } } QuickSort(arr,left,rightnumber) QuickSort(arr,leftnumber,right) }
|
4.三路快排
适合处理包含大量重复元素的数组
三路快速排序(3-Way QuickSort)是快速排序的一个优化版本,适用于数组中有许多重复元素的情况。在标准的快速排序中,数组会被划分成两部分:小于基准和大于基准,而三路快速排序会将数组划分为三部分:小于基准、等于基准和大于基准。这种划分方法有助于减少重复元素的处理,提高效率。
使用场景:
三路快速排序特别适用于数组中有大量重复元素的情况,因为它能够更好地处理这些元素,避免了普通快速排序在处理重复元素时性能下降的情况。
划分三部分:
性能分析:
c++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| void ThreeWayQuickSort(vector<int>&arr, int left, int right) { if (left >= right)return; int middle = (left + right) / 2; int middlenumber = arr[middle]; int leftindex = left; int rightindex = right; int index = left; while (index <= right) { if (arr[index] < middlenumber) { swap(arr[index], arr[leftindex]); index++; leftindex++; } else if (arr[index] > middlenumber) { swap(arr[index], arr[rightindex]); rightindex--; } else { index++; } } ThreeWayQuickSort(arr, left, leftindex - 1); ThreeWayQuickSort(arr, rightindex + 1, right); }
|
JavaScript:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| function threeWayQuickSort(arr, left, right) { if (left >= right) return; const middle = Math.floor((left + right) / 2); const middlenumber = arr[middle]; let leftIndex = left; let rightIndex = right; let index = left; while (index <= right) { if (arr[index] < middlenumber) { [arr[index], arr[leftIndex]] = [arr[leftIndex], arr[index]]; index++; leftIndex++; } else if (arr[index] > middlenumber) { [arr[index], arr[rightIndex]] = [arr[rightIndex], arr[index]]; rightIndex--; } else { index++; } } threeWayQuickSort(arr, left, leftIndex - 1); threeWayQuickSort(arr, rightIndex + 1, right); }
|
go:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| func threeWayQuickSort(arr []int, left, right int) { if left >= right { return } middle := (left + right) / 2 middlenumber, leftIndex, rightIndex, index := arr[middle], left, right, left for index <= rightIndex { if arr[index] < middlenumber { arr[index], arr[leftIndex] = arr[leftIndex], arr[index] leftIndex++ index++ } else if arr[index] > middlenumber { arr[index], arr[rightIndex] = arr[rightIndex], arr[index] rightIndex-- } else { index++ } } threeWayQuickSort(arr, left, leftIndex-1) threeWayQuickSort(arr, rightIndex+1, right) }
|
三.选择排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| void SelectSort(datatype arr[]) { int length = length_arr; for (int i = 0;i < length;i++) { int nums = i; for (int k = i + 1;k < length;k++) { if (arr[k] < arr[nums]) { nums = k; } } if (nums != i) { datatype data = arr[i]; arr[i] = arr[nums]; arr[nums] = data; } } }
|
四.堆排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
| void Headadjust(datatype arr[], int length, int i) { int topnumber = i; int leftnumber = 2 * i + 1; int rightnumber = 2 * i + 2; if (leftnumber<length && arr[leftnumber]>arr[topnumber]) { topnumber = leftnumber; HeapSortnums++; } if (rightnumber<length && arr[rightnumber]>arr[topnumber]) { topnumber = rightnumber; HeapSortnums++; } if (topnumber != i) { datatype data = arr[topnumber]; arr[topnumber] = arr[i]; arr[i] = data; Headadjust(arr, length, topnumber); } } void HeapSort(datatype arr[]) { int length = length_arr; for (int i = length / 2 - 1; i >= 0; i--) { Headadjust(arr, length, i); } for (int i = length; i > 0; i--) { datatype data = arr[0]; arr[0] = arr[i]; arr[i] = data; Headadjust(arr, i - 1, 0); } }
|
五.插入排序
1 2 3 4 5 6 7 8 9 10 11 12 13
| void InsertionSort(datatype arr[]) { int length = length_arr;int k; for (int i = 1;i < length;i++) { if (arr[i] < arr[i - 1]) { datatype temp = arr[i]; arr[i] = arr[i - 1]; for (k = i - 1;k>=0&&temp < arr[k];k--) { arr[k + 1] = arr[k]; } arr[k + 1] = temp; } } }
|
六.折半插入排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| void BinaryInsertionSort(datatype arr[]) { int length = length_arr;int k; for (int i = 1;i < length;i++) { datatype temp = arr[i]; int left = 0; int right = i - 1; while (right >= left) { int middle = left + (right - left) / 2; if (temp >= arr[middle]) { left = middle + 1; } else { right = middle - 1; } } for (k = i - 1;k >= right+1 && temp < arr[k];k--) { arr[k + 1] = arr[k]; } arr[k + 1] = temp; } }
|
七.希尔排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| void ShellSort(datatype arr[]) { int length = length_arr;int k; int opp = log(length) / log(2) - 1; int f = pow(2, opp) - 1; while (f >= 1) { for (int i = f;i < length;i++) { if (arr[i] < arr[i - f]) { datatype temp = arr[i]; arr[i] = arr[i - f]; for (k = i - f;k >= 0 && temp < arr[k];k--) { arr[k + f] = arr[k]; } arr[k + f] = temp; } } opp--; f = pow(2, opp) - 1; } }
|
八.归并排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| void Merging(datatype arr[], datatype temparr[], int leftnumber, int middlebumber, int rightnumber) { int left = leftnumber; int middle = middlebumber + 1; int start = leftnumber; while (left != middlebumber + 1 && middle != rightnumber + 1) { if (arr[left] <= arr[middle]) { temparr[start++] = arr[left++]; } else { temparr[start++] = arr[middle++]; } } while (left != middlebumber + 1) { temparr[start++] = arr[left++]; } while (middle != rightnumber + 1) { temparr[start++] = arr[middle++]; } for (int i = leftnumber;i <= rightnumber;i++) { arr[i] = temparr[i]; } } void MergingSort(datatype arr[],datatype temparr[],int leftnumber,int rightnumber) { int middlenumber; if (rightnumber > leftnumber) { middlenumber = (rightnumber + leftnumber) / 2; MergingSort(arr, temparr, leftnumber, middlenumber); MergingSort(arr, temparr, middlenumber+1, rightnumber); Merging(arr, temparr, leftnumber, middlenumber, rightnumber); } }
|
九.基数排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
| int maxdatabit(datatype arr[]) { int length = length_arr; datatype data = 0; int databit = 0; for (int i = 0;i < length;i++) { if (arr[i] > data) { data = arr[i]; } } while (data) { databit++; data /= 10; } return databit; } void RadixSort(datatype arr[]) { int length = length_arr; int indexnubmer; int max_bit = maxdatabit(arr); for (int i = 0;i < max_bit;i++) { int collectdata[10] = { 0 }; int temparr[length_arr]; for (int j = 0;j < length;j++) { int index = (arr[j] / indexnubmer) % 10; collectdata[index]++; } for (int j = 1; j < 10; j++) { collectdata[j] += collectdata[j - 1]; } for (int j = length - 1; j >= 0; j--) { int index = (arr[j] / indexnubmer) % 10; temparr[collectdata[index] - 1] = arr[j]; collectdata[index]--; } for (int k = 0;k < length;k++) { arr[k] = temparr[k]; } delete[] temparr; indexnubmer = indexnubmer * 10; } }
|