前言
常用排序算法有冒泡排序、快速排序、插入排序、选择排序、希尔排序、归并排序、堆排序等。
一、排序算法
1.原理简述
1. 冒泡排序
比较相邻的元素，将较大的元素交换至右端。
2. 选择排序
在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
3. 插入排序
将未排序元素插入到已排序序列中，位置选择正确的位置。
4. 希尔排序
将数组分割成多个子序列，分别进行插入排序。
5. 归并排序
将两个或两个以上的有序序列合并成一个新的有序序列。
6. 快速排序
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
7. 堆排序
将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
2.分类与复杂度
二、实例代码
1.冒泡排序
C
void bubble_sort(int arr[], int n) { int i, j; for (i = 0; i < n-1; i++) for (j = 0; j < n-i-1; j++) if (arr[j] > arr[j+1]) swap(&arr[j], &arr[j+1]); }
Python
def bubble_sort(nums): for i in range(len(nums)-1): for j in range(len(nums)-i-1): if nums[j] > nums[j+1]: nums[j], nums[j+1] = nums[j+1], nums[j] return nums
Java
public static void bubbleSort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } }
Golang
func BubbleSort(arr []int) { for i := 0; i < len(arr); i++ { for j := 0; j < len(arr)-i-1; j++ { if arr[j] > arr[j+1] { arr[j], arr[j+1] = arr[j+1], arr[j] } } } }
Rust
fn bubble_sort(arr: &mut [i32]) { let len = arr.len(); for i in 0..len { for j in 0..len - i - 1 { if arr[j] > arr[j + 1] { arr.swap(j, j + 1); } } } }
Dephi
procedure BubbleSort(var A: array of Integer); var I, J, T: Integer; begin for I := Low(A) to High(A) - 1 do for J := I + 1 to High(A) do if A[I] > A[J] then begin T := A[I]; A[I] := A[J]; A[J] := T; end; end;
2.选择排序
C
void selection_sort(int arr[], int n) { int i, j, min_idx; for (i = 0; i < n-1; i++) { min_idx = i; for (j = i+1; j < n; j++) if (arr[j] < arr[min_idx]) min_idx = j; swap(&arr[min_idx], &arr[i]); } }
Python
def selection_sort(nums): for i in range(len(nums)-1): min_index = i for j in range(i+1, len(nums)): if nums[j] < nums[min_index]: min_index = j nums[i], nums[min_index] = nums[min_index], nums[i] return nums
Java
public static void selectionSort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { int minIndex = i; for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } }
Golang
func SelectionSort(arr []int) { for i := 0; i < len(arr); i++ { minIndex := i for j := i + 1; j < len(arr); j++ { if arr[j] < arr[minIndex] { minIndex = j } } arr[i], arr[minIndex] = arr[minIndex], arr[i] } }
Rust
fn selection_sort(arr: &mut [i32]) { let len = arr.len(); for i in 0..len { let mut min_index = i; for j in i + 1..len { if arr[j] < arr[min_index] { min_index = j; } } arr.swap(i, min_index); } }
Dephi
procedure SelectionSort(var A: array of Integer); var I, J, Min, T: Integer; begin for I := Low(A) to High(A) - 1 do begin Min := I; for J := I + 1 to High(A) do if A[J] < A[Min] then Min := J; T := A[Min]; A[Min] := A[I]; A[I] := T; end; end;
3.插入排序
C
void insertion_sort(int arr[], int n) { int i, key, j; for (i = 1; i < n; i++) { key = arr[i]; j = i-1; while (j >= 0 && arr[j] > key) { arr[j+1] = arr[j]; j = j-1; } arr[j+1] = key; } }
Python
def insertion_sort(nums): for i in range(1, len(nums)): j = i while j > 0 and nums[j] < nums[j-1]: nums[j], nums[j-1] = nums[j-1], nums[j] j -= 1 return nums
Java
public static void insertionSort(int[] arr) { int n = arr.length; for (int i = 1; i < n; i++) { int value = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > value) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = value; } }
Golang
func InsertionSort(arr []int) { for i := 1; i < len(arr); i++ { for j := i; j > 0; j-- { if arr[j] < arr[j-1] { arr[j], arr[j-1] = arr[j-1], arr[j] } } } }
Rust
fn Insertion_sort(arr: &mut [i32]) { let len = arr.len(); for i in 1..len { let mut j = i; while j > 0 && arr[j] < arr[j - 1] { arr.swap(j, j - 1); j -= 1; } } }
Dephi
procedure InsertionSort(var A: array of Integer); var I, J, T: Integer; begin for I := Low(A) + 1 to High(A) do begin T := A[I]; J := I - 1; while (J >= Low(A)) and (A[J] > T) do begin A[J + 1] := A[J]; Dec(J); end; A[J + 1] := T; end; end;
4.希尔排序
C
void Shell_sort(int arr[], int n) { for (int gap = n/2; gap > 0; gap /= 2) { for (int i = gap; i < n; i += 1) { int temp = arr[i]; int j; for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) arr[j] = arr[j - gap]; arr[j] = temp; } } }
Python
def shell_sort(nums): gap = len(nums) // 2 while gap > 0: for i in range(gap, len(nums)): j = i while j >= gap and nums[j] < nums[j-gap]: nums[j], nums[j-gap] = nums[j-gap], nums[j] j -= gap gap //= 2 return nums
Java
public static void shellSort(int[] arr) { int n = arr.length; for (int gap = n / 2; gap > 0; gap /= 2) { for (int i = gap; i < n; i++) { int value = arr[i]; int j = i - gap; while (j >= 0 && arr[j] > value) { arr[j + gap] = arr[j]; j -= gap; } arr[j + gap] = value; } } }
Golang
func ShellSort(arr []int) { n := len(arr) h := 1 for h < n/3 { h = 3*h + 1 } for h >= 1 { for i := h; i < n; i++ { for j := i; j >= h && arr[j] < arr[j-h]; j -= h { arr[j], arr[j-h] = arr[j-h], arr[j] } } h /= 3 } }
Rust
fn shell_sort(arr: &mut [i32]) { let len = arr.len(); let mut gap = len / 2; while gap > 0 { for i in gap..len { let mut j = i; while j >= gap && arr[j - gap] > arr[j] { arr.swap(j - gap, j); j -= gap; } } gap /= 2; } }
Dephi
procedure ShellSort(var A: array of Integer); var I, J, T, Gap: Integer; begin Gap := High(A) div 2; while Gap > 0 do begin for I := Gap to High(A) do begin T := A[I]; J := I; while (J >= Gap) and (A[J - Gap] > T) do begin A[J] := A[J - Gap]; J := J - Gap; end; A[J] := T; end; Gap := Gap div 2; end; end;
5.归并排序
C
void merge(int arr[], int l, int m, int r) { int i, j, k; int n1 = m - l + 1; int n2 = r - m; int L[n1], R[n2]; for (i = 0; i < n1; i++) L[i] = arr[l + i]; for (j = 0; j < n2; j++) R[j] = arr[m + 1+ j]; i = 0; j = 0; k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; } } void merge_sort(int arr[], int l, int r) { if (l < r) { int m = l+(r-l)/2; merge_sort(arr, l, m); merge_sort(arr, m+1, r); merge(arr, l, m, r); } }
Python
#归并排序： def merge_sort(nums): if len(nums) <= 1: return nums mid = len(nums) // 2 left = merge_sort(nums[:mid]) right = merge_sort(nums[mid:]) return merge(left, right) def merge(left, right): res = [] while left and right: if left[0] <= right[0]: res.append(left.pop(0)) else: res.append(right.pop(0)) res += left res += right return res
Java
public static void mergeSort(int[] arr) { int n = arr.length; if (n < 2) { return; } int mid = n / 2; int[] left = new int[mid]; int[] right = new int[n - mid]; for (int i = 0; i < mid; i++) { left[i] = arr[i]; } for (int i = mid; i < n; i++) { right[i - mid] = arr[i]; } mergeSort(left); mergeSort(right); merge(arr, left, right); } public static void merge(int[] arr, int[] left, int[] right) { int i = 0, j = 0, k = 0; int leftLen = left.length; int rightLen = right.length; while (i < leftLen && j < rightLen) { if (left[i] <= right[j]) { arr[k++] = left[i++]; } else { arr[k++] = right[j++]; } } while (i < leftLen) { arr[k++] = left[i++]; } while (j < rightLen) { arr[k++] = right[j++]; } }
Golang
func MergeSort(arr []int) { if len(arr) <= 1 { return } mid := len(arr) / 2 left := arr[:mid] right := arr[mid:] MergeSort(left) MergeSort(right) i := 0 j := 0 k := 0 for i < len(left) && j < len(right) { if left[i] < right[j] { arr[k] = left[i] i++ } else { arr[k] = right[j] j++ } k++ } for i < len(left) { arr[k] = left[i] i++ k++ } for j < len(right) { arr[k] = right[j] j++ k++ } }
Rust
fn merge_sort(arr: &mut [i32]) { let len = arr.len(); if len > 1 { let mid = len / 2; merge_sort(&mut arr[..mid]); merge_sort(&mut arr[mid..]); merge(arr, mid); } } fn merge(arr: &mut [i32], mid: usize) { let mut left = 0; let mut right = mid; let mut temp = Vec::with_capacity(arr.len()); while left < mid && right < arr.len() { if arr[left] <= arr[right] { temp.push(arr[left]); left += 1; } else { temp.push(arr[right]); right += 1; } } while left < mid { temp.push(arr[left]); left += 1; } while right < arr.len() { temp.push(arr[right]); right += 1; } for i in 0..arr.len() { arr[i] = temp[i]; } }
Dephi
procedure MergeSort(var A: array of Integer; Low, High: Integer); var Mid: Integer; begin if Low < High then begin Mid := (Low + High) div 2; MergeSort(A, Low, Mid); MergeSort(A, Mid + 1, High); Merge(A, Low, Mid, High); end; end;
6.快速排序
C
int partition (int arr[], int low, int high) { int pivot = arr[high]; int i = (low - 1); for (int j = low; j <= high- 1; j++) { if (arr[j] <= pivot) { i++; swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return (i + 1); } void quick_sort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); quick_sort(arr, low, pi - 1); quick_sort(arr, pi + 1, high); } }
Python
# 快速排序： def quick_sort(nums): if len(nums) <= 1: return nums pivot = nums[0] left = [x for x in nums[1:] if x < pivot] right = [x for x in nums[1:] if x >= pivot] return quick_sort(left) + [pivot] + quick_sort(right)
Java
public static void quickSort(int[] arr, int low, int high) { if (low < high) { int pivot = partition(arr, low, high); quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); } } public static int partition(int[] arr, int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] <= pivot) { i++; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp; return i + 1; }
Golang
func QuickSort(arr []int) { if len(arr) <= 1 { return } pivot := arr[0] left := []int{} right := []int{} for i := 1; i < len(arr); i++ { if arr[i] < pivot { left = append(left, arr[i]) } else { right = append(right, arr[i]) } } QuickSort(left) QuickSort(right) arr = append(append(left, pivot), right...) }
Rust
fn quick_sort(arr: &mut [i32]) { let len = arr.len(); if len > 1 { let pivot = partition(arr); quick_sort(&mut arr[..pivot]); quick_sort(&mut arr[pivot + 1..]); } } fn partition(arr: &mut [i32]) -> usize { let len = arr.len(); let pivot = arr[len - 1]; let mut i = 0; for j in 0..len - 1 { if arr[j] < pivot { arr.swap(i, j); i += 1; } } arr.swap(i, len - 1); }
Dephi
procedure QuickSort(var A: array of Integer; Low, High: Integer); var I, J, Pivot: Integer; begin if Low < High then begin Pivot := A[Low]; I := Low; J := High; repeat while A[I] < Pivot do Inc(I); while A[J] > Pivot do Dec(J); if I <= J then begin Swap(A[I], A[J]); Inc(I); Dec(J); end; until I > J; if Low < J then QuickSort(A, Low, J); if I < High then QuickSort(A, I, High); end; end;
7.堆排序
C
void heapify(int arr[], int n, int i) { int largest = i; int l = 2*i + 1; int r = 2*i + 2; if (l < n && arr[l] > arr[largest]) largest = l; if (r < n && arr[r] > arr[largest]) largest = r; if (largest != i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); } } void heap_sort(int arr[], int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); for (int i=n-1; i>=0; i--) { swap(arr[0], arr[i]); heapify(arr, i, 0); } }
Python
# 堆排序： def heap_sort(nums): n = len(nums) for i in range(n//2-1, -1, -1): heapify(nums, n, i) for i in range(n-1, 0, -1): nums[i], nums[0] = nums[0], nums[i] heapify(nums, i, 0) return nums def heapify(nums, n, i): largest = i l = 2*i + 1 r = 2*i + 2 if l < n and nums[i] < nums[l]: largest = l if r < n and nums[largest] < nums[r]: largest = r if largest != i: nums[i], nums[largest] = nums[largest], nums[i] heapify(nums, n, largest)
Java
public static void heapSort(int[] arr) { int n = arr.length; for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } for (int i = n - 1; i >= 0; i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapify(arr, i, 0); } } public static void heapify(int[] arr, int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && arr[left] > arr[largest]) { largest = left; } if (right < n && arr[right] > arr[largest]) { largest = right; } if (largest != i) { int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; heapify(arr, n, largest); } }
Golang
func HeapSort(arr []int) { n := len(arr) for i := n/2 - 1; i >= 0; i-- { heapify(arr, n, i) } for i := n - 1; i >= 0; i-- { arr[0], arr[i] = arr[i], arr[0] heapify(arr, i, 0) } } func heapify(arr []int, n, i int) { largest := i l := 2*i + 1 r := 2*i + 2 if l < n && arr[l] > arr[largest] { largest = l } if r < n && arr[r] > arr[largest] { largest = r } if largest != i { arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest) } }
Rust
fn heap_sort(arr: &mut [i32]) { let len = arr.len(); for i in (0..len / 2).rev() { heapify(arr, i, len); } for i in (1..len).rev() { arr.swap(0, i); heapify(arr, 0, i); } } fn heapify(arr: &mut [i32], i: usize, len: usize) { let mut largest = i; let left = 2 * i + 1; let right = 2 * i + 2; if left < len && arr[left] > arr[largest] { largest = left; } if right < len && arr[right] > arr[largest] { largest = right; } if largest != i { arr.swap(i, largest); heapify(arr, largest, len); } }
Dephi
procedure HeapSort(var A: array of Integer); var I, T: Integer; begin BuildHeap(A); for I := High(A) downto Low(A) + 1 do begin T := A[Low(A)]; A[Low(A)] := A[I]; A[I] := T; Heapify(A, Low(A), I - 1); end; end;
总结
