广州网站建设360网站优化,英文网站建设口碑好,制作网页时用什么实现动态效果,效果好的网站制作文章目录 十大经典排序算法比较排序1. 冒泡排序2. 选择排序3. 插入排序4. 希尔排序5. 归并排序6. 快速排序7. 堆排序 非比较排序8. 计数排序9. 桶排序10. 基数排序 十大经典排序算法
十大经典排序算法可以分为比较排序和非比较排序: 前者包括冒泡排序、选择排序、插入排序、希… 文章目录 十大经典排序算法比较排序1. 冒泡排序2. 选择排序3. 插入排序4. 希尔排序5. 归并排序6. 快速排序7. 堆排序 非比较排序8. 计数排序9. 桶排序10. 基数排序 十大经典排序算法
十大经典排序算法可以分为比较排序和非比较排序: 前者包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序; 后者包括计数排序、桶排序、基数排序;
下面将详细介绍这些算法
比较排序
1. 冒泡排序
基本思想重复地走访要排序的数列一次比较两个数据元素如果顺序不对则进行交换并一直重复这样的走访操作直到没有要交换的数据元素为止。代码示例
void bubbleSort(int arr[], int n) {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;}}}
}def bubble_sort(arr):n len(arr)for i in range(n):for j in range(0, n-i-1):if arr[j] arr[j1]:arr[j], arr[j1] arr[j1], arr[j]return arr解释 该函数接受一个列表 arr 作为输入。 外层循环 for i in range(n) 控制排序的轮数每一轮将最大元素 “浮” 到末尾。 内层循环 for j in range(0, n-i-1) 比较相邻元素如果顺序错误则交换它们的位置。 时间复杂度最好情况为 O ( n ) O(n) O(n)最坏情况为 O ( n 2 ) O(n^2) O(n2)。 空间复杂度 O ( 1 ) O(1) O(1)。
2. 选择排序
基本思想首先在未排序序列中找到最小大元素存放到排序序列的起始位置然后再从剩余未排序元素中继续寻找最小大元素然后放到已排序序列的末尾。以此类推直到所有元素均排序完毕。代码示例
void selectionSort(int arr[], int n) {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;}
}def selection_sort(arr):for i in range(len(arr)):min_index ifor j in range(i1, len(arr)):if arr[j] arr[min_index]:min_index jarr[i], arr[min_index] arr[min_index], arr[i]return arr解释 函数 selection_sort 对列表 arr 进行排序。 外层循环 for i in range(len(arr)) 确定当前要放置最小元素的位置。 内层循环 for j in range(i1, len(arr)) 寻找未排序部分的最小元素索引。 时间复杂度 O ( n 2 ) O(n^2) O(n2)。 空间复杂度 O ( 1 ) O(1) O(1)。
3. 插入排序
基本思想对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。代码示例
void insertionSort(int arr[], int n) {for (int i 1; i n; i) {int key arr[i];int j i - 1;while (j 0 arr[j] key) {arr[j 1] arr[j];j--;}arr[j 1] key;}
}def insertion_sort(arr):for i in range(1, len(arr)):key arr[i]j i - 1while j 0 and key arr[j]:arr[j 1] arr[j]j - 1arr[j 1] keyreturn arr解释 该函数接受列表 arr 并对其排序。 从第二个元素开始将元素 key 与其前面已排序部分的元素比较并插入正确位置。 时间复杂度最好情况为 O ( n ) O(n) O(n)最坏情况为 O ( n 2 ) O(n^2) O(n2)。 空间复杂度 O ( 1 ) O(1) O(1)。
4. 希尔排序
基本思想先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序待整个序列中的记录 “基本有序” 时再对全体记录进行依次直接插入排序。代码示例
void shellSort(int arr[], int n) {for (int gap n / 2; gap 0; gap / 2) {for (int i gap; i n; i) {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;}}
}def shell_sort(arr):n len(arr)gap n // 2while gap 0:for i in range(gap, n):temp arr[i]j iwhile j gap and arr[j - gap] temp:arr[j] arr[j - gap]j - gaparr[j] tempgap // 2return arr函数 shell_sort 进行希尔排序。 初始 gap 为 n // 2对相隔 gap 的元素进行插入排序不断缩小 gap 直至为 1。 时间复杂度 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n) 到 O ( n 2 ) O(n^2) O(n2) 之间。 空间复杂度 O ( 1 ) O(1) O(1)。
5. 归并排序
基本思想将一个数组分成两个子数组对每个子数组递归地进行排序然后将排序好的子数组合并成一个有序的数组。代码示例
void merge(int arr[], int l, int m, int r) {int n1 m - l 1;int n2 r - m;int L[n1], R[n2];for (int i 0; i n1; i)L[i] arr[l i];for (int j 0; j n2; j)R[j] arr[m 1 j];int 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 mergeSort(int arr[], int l, int r) {if (l r) {int m l (r - l) / 2;mergeSort(arr, l, m);mergeSort(arr, m 1, r);merge(arr, l, m, r);}
}def merge_sort(arr):if len(arr) 1:mid len(arr) // 2L arr[:mid]R arr[mid:]merge_sort(L)merge_sort(R)i j k 0while i len(L) and j len(R):if L[i] R[j]:arr[k] L[i]i 1else:arr[k] R[j]j 1k 1while i len(L):arr[k] L[i]i 1k 1while j len(R):arr[k] R[j]j 1k 1return arrmerge_sort 函数将列表不断二分分别对左右子列表排序最后合并。 递归调用 merge_sort 对左右子列表排序。 时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)。 空间复杂度 O ( n ) O(n) O(n)。
6. 快速排序
基本思想通过一趟排序将待排记录分隔成独立的两部分其中一部分记录的关键字均比另一部分的关键字小则可分别对这两部分记录继续进行排序以达到整个序列有序。代码示例
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;
}
void quickSort(int arr[], int low, int high) {if (low high) {int pi partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi 1, high);}
}def quick_sort(arr):if len(arr) 1:return arrpivot arr[len(arr) // 2]left [x for x in arr if x pivot]middle [x for x in arr if x pivot]right [x for x in arr if x pivot]return quick_sort(left) middle quick_sort(right)解释 函数 quick_sort 选择一个基准元素 pivot。 元素被分成小于、等于、大于 pivot 的三个部分对小于和大于部分递归排序。 时间复杂度最好情况为 O ( n l o g n ) O(nlogn) O(nlogn)最坏情况为 O ( n 2 ) O(n^2) O(n2)。 空间复杂度 O ( l o g n ) O(logn) O(logn)到 O ( n ) O(n) O(n)。
7. 堆排序
基本思想将待排序序列构造成一个大顶堆此时整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换此时末尾就为最大值。然后将剩余个元素重新构造成一个堆这样会得到个元素的次小值。如此反复执行便能得到一个有序序列了。代码示例
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) {int temp arr[i];arr[i] arr[largest];arr[largest] temp;heapify(arr, n, largest);}
}
void heapSort(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--) {int temp arr[0];arr[0] arr[i];arr[i] temp;heapify(arr, i, 0);}
}def heapify(arr, n, i):largest il 2 * i 1r 2 * i 2if l n and arr[i] arr[l]:largest lif r n and arr[largest] arr[r]:largest rif largest! i:arr[i], arr[largest] arr[largest], arr[i]heapify(arr, n, largest)def heap_sort(arr):n len(arr)for i in range(n // 2 - 1, -1, -1):heapify(arr, n, i)for i in range(n - 1, 0, -1):arr[i], arr[0] arr[0], arr[i]heapify(arr, i, 0)return arr解释 heapify 函数用于维护堆的性质。 heap_sort 先将数组构建成最大堆然后不断交换堆顶元素与末尾元素并调整堆。 时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)。 空间复杂度 O ( 1 ) O(1) O(1)。
非比较排序
8. 计数排序
基本思想通过统计每个元素出现的次数然后根据统计结果将元素依次放入有序序列中。代码示例
void countSort(int arr[], int n) {int max arr[0];for (int i 1; i n; i) {if (arr[i] max) {max arr[i];}}int count[max 1];for (int i 0; i max; i) {count[i] 0;}for (int i 0; i n; i) {count[arr[i]];}int j 0;for (int i 0; i max; i) {while (count[i] 0) {arr[j] i;j;count[i]--;}}
}def count_sort(arr):max_val max(arr)count [0] * (max_val 1)for i in arr:count[i] 1output []for i in range(len(count)):for j in range(count[i]):output.append(i)return output解释 count_sort 先统计元素出现次数。 然后根据计数数组将元素按序添加到输出列表。 时间复杂度 O ( n k ) O(nk) O(nk) k k k其中是数据的范围。 空间复杂度 O ( k ) O(k) O(k)。
9. 桶排序
基本思想将数据分到有限数量的桶子里每个桶子再分别排序有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序。代码示例
#include iostream
#include vector
#include algorithm
using namespace std;
void bucketSort(double arr[], int n) {vectordouble buckets[n];for (int i 0; i n; i) {int bucketIndex n * arr[i];buckets[bucketIndex].push_back(arr[i]);}for (int i 0; i n; i) {sort(buckets[i].begin(), buckets[i].end());}int index 0;for (int i 0; i n; i) {for (int j 0; j buckets[i].size(); j) {arr[index] buckets[i][j];index;}}
}def bucket_sort(arr):if len(arr) 0:return arrmin_val, max_val min(arr), max(arr)bucket_size 5bucket_count (max_val - min_val) // bucket_size 1buckets [[] for _ in range(bucket_count)]for i in arr:buckets[(i - min_val) // bucket_size].append(i)sorted_arr []for bucket in buckets:insertion_sort(bucket)sorted_arr.extend(bucket)return sorted_arr解释 函数 bucket_sort 把元素分散到多个桶中。 对每个桶中的元素使用插入排序并合并。 时间复杂度 O ( n k ) O(nk) O(nk)其中 k k k 是桶的数量。 空间复杂度 O ( n k ) O(nk) O(nk)。
10. 基数排序 基本思想将所有待比较数值正整数统一为同样的数位长度数位较短的数前面补零。然后从最低位开始依次进行一次排序。这样从最低位排序一直到最高位排序完成以后数列就变成一个有序序列。代码示例
void countSortForRadix(int arr[], int n, int exp) {int output[n];int count[10] { 0 };for (int i 0; i n; i) {count[(arr[i] / exp) % 10];}for (int i 1; i 10; i) {count[i] count[i - 1];}for (int i n - 1; i 0; i--) {output[count[(arr[i] / exp) % 10] - 1] arr[i];count[(arr[i] / exp) % 10]--;}for (int i 0; i n; i) {arr[i] output[i];}
}
void radixSort(int arr[], int n) {int maxVal arr[0];for (int i 1; i n; i) {if (arr[i] maxVal) {maxVal arr[i];}}for (int exp 1; maxVal / exp 0; exp * 10) {countSortForRadix(arr, n, exp);}
}def radix_sort(arr):def get_digit(num, digit):return (num // 10**digit) % 10max_val max(arr)exp 0while 10**exp max_val:buckets [[] for _ in range(10)]for i in arr:digit get_digit(i, exp)buckets[digit].append(i)arr []for bucket in buckets:arr.extend(bucket)exp 1return arr解释
radix_sort 对元素按不同位数排序。从最低位开始将元素放入对应数字的桶中再合并逐位推进。
你可以使用以下方式调用这些函数
arr [12, 11, 13, 5, 6]
print(bubble_sort(arr.copy()))
print(selection_sort(arr.copy()))
print(insertion_sort(arr.copy()))
print(shell_sort(arr.copy()))
print(merge_sort(arr.copy()))
print(quick_sort(arr.copy()))
print(heap_sort(arr.copy()))
print(count_sort(arr.copy()))
print(bucket_sort(arr.copy()))
print(radix_sort(arr.copy()))以上代码通过不同的排序算法实现了对列表的排序并且通过使用 copy 避免原始列表被修改。
注意 在使用 bucket_sort 时这里使用了 insertion_sort 对桶内元素排序可以使用其他排序算法。 在 radix_sort 中根据不同位数将元素放入不同桶按顺序取出实现排序。 时间复杂度 O ( d ( n k ) O(d(nk) O(d(nk)其中 d d d 是数字的位数 k k k 是基数。 空间复杂度 O ( n k ) O(nk) O(nk)。
