文章目錄

前言

一、排序算法

1.原理簡(jiǎn)述

2.分類(lèi)與復(fù)雜度

二、實(shí)例代碼

1.冒泡排序

C

Python

Java

Golang

Rust

Dephi

2.選擇排序

C

Python

Java

?Golang

?Rust

?Dephi

3.插入排序

C

Python

Java

?Golang

?Rust

?Dephi

4.希爾排序

?編輯

C

Python

Java

?Golang

?Rust

?Dephi

5.歸并排序

C

Python

Java

?Golang

?Rust

?Dephi

6.快速排序

C

Python

Java

?Golang

?Rust

?Dephi

7.堆排序

C

Python

Java

Golang

Rust

?Dephi

總結(jié)

---

前言

常用排序算法有冒泡排序、快速排序、插入排序、選擇排序、希爾排序、歸并排序、堆排序等。

---

一、排序算法

1.原理簡(jiǎn)述

1. 冒泡排序

比較相鄰的元素，將較大的元素交換至右端。

2. 選擇排序

在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

3. 插入排序

將未排序元素插入到已排序序列中，位置選擇正確的位置。

4. 希爾排序

將數(shù)組分割成多個(gè)子序列，分別進(jìn)行插入排序。

5. 歸并排序

將兩個(gè)或兩個(gè)以上的有序序列合并成一個(gè)新的有序序列。

6. 快速排序

通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

7. 堆排序

將待排序序列構(gòu)造成一個(gè)大頂堆，此時(shí)，整個(gè)序列的最大值就是堆頂?shù)母?jié)點(diǎn)。將其與末尾元素進(jìn)行交換，此時(shí)末尾就為最大值。然后將剩余n-1個(gè)元素重新構(gòu)造成一個(gè)堆，這樣會(huì)得到n個(gè)元素的次小值。如此反復(fù)執(zhí)行，便能得到一個(gè)有序序列了。

2.分類(lèi)與復(fù)雜度

大類(lèi)	算法	時(shí)間復(fù)雜度	穩(wěn)定性
交換排序	冒泡排序	O(n^2)	穩(wěn)定
	快速排序	O(nlogn)
選擇排序	選擇排序	O(n^2)
	堆排序	O(nlogn)
插入排序	插入排序	O(n^2)	穩(wěn)定
	希爾排序	O(n^(1.3~1.5))
歸并排序	歸并排序	O(nlogn)	穩(wěn)定

二、實(shí)例代碼

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);
varI, J, T: Integer;
beginfor I := Low(A) to High(A) - 1 dofor J := I + 1 to High(A) doif A[I] > A[J] thenbeginT := 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 = ifor j in range(i+1, len(nums)):if nums[j] < nums[min_index]:min_index = jnums[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 := ifor 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);
varI, J, Min, T: Integer;
beginfor I := Low(A) to High(A) - 1 dobeginMin := I;for J := I + 1 to High(A) doif A[J] < A[Min] thenMin := 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 = iwhile j > 0 and nums[j] < nums[j-1]:nums[j], nums[j-1] = nums[j-1], nums[j]j -= 1return 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);
varI, J, T: Integer;
beginfor I := Low(A) + 1 to High(A) dobeginT := A[I];J := I - 1;while (J >= Low(A)) and (A[J] > T) dobeginA[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) // 2while gap > 0:for i in range(gap, len(nums)):j = iwhile j >= gap and nums[j] < nums[j-gap]:nums[j], nums[j-gap] = nums[j-gap], nums[j]j -= gapgap //= 2return 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 := 1for 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);
varI, J, T, Gap: Integer;
beginGap := High(A) div 2;while Gap > 0 dobeginfor I := Gap to High(A) dobeginT := A[I];J := I;while (J >= Gap) and (A[J - Gap] > T) dobeginA[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 numsmid = len(nums) // 2left = 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 += leftres += rightreturn 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) / 2left := arr[:mid]right := arr[mid:]MergeSort(left)MergeSort(right)i := 0j := 0k := 0for 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);
varMid: Integer;
beginif Low < High thenbeginMid := (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 numspivot = 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);
varI, J, Pivot: Integer;
beginif Low < High thenbeginPivot := A[Low];I := Low;J := High;repeatwhile A[I] < Pivot doInc(I);while A[J] > Pivot doDec(J);if I <= J thenbeginSwap(A[I], A[J]);Inc(I);Dec(J);end;until I > J;if Low < J thenQuickSort(A, Low, J);if I < High thenQuickSort(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 numsdef heapify(nums, n, i):largest = il = 2*i + 1r = 2*i + 2if l < n and nums[i] < nums[l]:largest = lif r < n and nums[largest] < nums[r]:largest = rif 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 := il := 2*i + 1r := 2*i + 2if 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);
varI, T: Integer;
beginBuildHeap(A);for I := High(A) downto Low(A) + 1 dobeginT := A[Low(A)];A[Low(A)] := A[I];A[I] := T;Heapify(A, Low(A), I - 1);end;
end;

---

總結(jié)

???作者：Hann Yang

???主頁(yè)：CSDN主頁(yè)

???2022博客之星Top58，原力榜Top10/作者周榜Top13
???“搶走你工作的不會(huì)是 AI ，而是先掌握 AI 能力的人”