o2o网站建设方案,自己做的网站可以百度推广吗,业余做网站,网络营销代运营外包公司文章目录
前言
一、排序算法
1.原理简述
2.分类与复杂度
二、实例代码
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 Gola…文章目录
前言
一、排序算法
1.原理简述
2.分类与复杂度
二、实例代码
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
总结 前言
常用排序算法有冒泡排序、快速排序、插入排序、选择排序、希尔排序、归并排序、堆排序等。 一、排序算法
1.原理简述
1. 冒泡排序
比较相邻的元素将较大的元素交换至右端。
2. 选择排序
在未排序序列中找到最小大元素存放到排序序列的起始位置。
3. 插入排序
将未排序元素插入到已排序序列中位置选择正确的位置。
4. 希尔排序
将数组分割成多个子序列分别进行插入排序。
5. 归并排序
将两个或两个以上的有序序列合并成一个新的有序序列。
6. 快速排序
通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列。
7. 堆排序
将待排序序列构造成一个大顶堆此时整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆这样会得到n个元素的次小值。如此反复执行便能得到一个有序序列了。
2.分类与复杂度
大类算法时间复杂度稳定性交换排序冒泡排序O(n^2)稳定快速排序O(nlogn) 选择排序选择排序O(n^2) 堆排序O(nlogn) 插入排序插入排序O(n^2)稳定希尔排序O(n^(1.3~1.5)) 归并排序归并排序O(nlogn)稳定
二、实例代码
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[j1]) swap(arr[j], arr[j1]);
} Python
def bubble_sort(nums):for i in range(len(nums)-1):for j in range(len(nums)-i-1):if nums[j] nums[j1]:nums[j], nums[j1] nums[j1], 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[j1] {arr[j], arr[j1] arr[j1], 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 i1; 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(i1, 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[j1] arr[j]; j j-1; } arr[j1] 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, m1, 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]ik}for j len(right) {arr[k] right[j]jk}
} 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 in-1; i0; 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; 总结 ♥️ 作者Hann Yang ♥️ 主页CSDN主页 ♥️ 2022博客之星Top58原力榜Top10/作者周榜Top13 ♥️ “抢走你工作的不会是 AI 而是先掌握 AI 能力的人”
