贵州省建设厅网站,查询备案号怎么查询,北京移动端网站多少钱,Wordpress 淘宝客 页面文章目录 常见的排序算法类型复杂度和稳定性 1.冒泡排序2.直接插入排序3.希尔排序4.简单选择排序方法1#xff1a;双向遍历选择排序方法2#xff1a;单向遍历选择排序 5.归并排序方法1#xff1a;递归方法2#xff1a;非递归 6.快速排序方法1#xff1a;随机取keyi方法2双向遍历选择排序方法2单向遍历选择排序 5.归并排序方法1递归方法2非递归 6.快速排序方法1随机取keyi方法2三数取中方法3挖坑法方法4前后指针法方法5:非递归方法6三路划分 7.堆排序8.计数排序9.基数排序9.桶排序 常见的排序算法
类型 复杂度和稳定性
数据结构的复杂度和稳定性是评价数据结构优劣的两个方面复杂度主要关注数据结构在执行操作时所需的时间和空间资源消耗而稳定性主要关注数据结构在执行操作时是否能够保证原有数据的相对位置不变。 1.冒泡排序 这是一个冒泡排序算法的实现它可以对一个整型数组按照从大到小的顺序进行排序。
算法的基本思想是通过不断比较相邻的元素并交换它们的位置将较大的元素逐渐“冒泡”到数组的顶端。具体来说该算法通过双重循环实现外层循环控制比较的轮数内层循环负责相邻元素的比较和交换操作。在每一轮比较中如果当前元素比它后面的元素小就交换它们的位置使得较大的元素逐渐向数组的前部移动。
该算法的时间复杂度为O(n^2)其中n为数组的长度。虽然它的时间复杂度较高但是它的实现简单、容易理解对于小规模的数据排序来说还是比较实用的。
//从小到大
void BubbleSort1(int* a, int n)
{for (int i 0; i n-1; i){for (int j 0; j n - 1 - i; j){if (a[j] a[j 1]){int temp a[j];a[j] a[j 1];a[j 1] temp;}}}
}这也是一个冒泡排序算法的实现可以对一个整型数组按照从小到大的顺序进行排序。
与上一个算法相比该算法的唯一区别在于内层循环中比较的方式。在该算法中如果当前元素比它后面的元素大就交换它们的位置使得较小的元素逐渐向数组的前部移动。
该算法的时间复杂度同样为O(n^2)其中n为数组的长度。由于冒泡排序算法的优化空间比较有限因此它的时间复杂度较高不适合用于大规模数据的排序。
//从大到小
void BubbleSort2(int* a, int n)
{for (int i 0; i n - 1; i){for (int j 0; j n - 1 - i; j){if (a[j] a[j 1]){int temp a[j];a[j] a[j 1];a[j 1] temp;}}}
}2.直接插入排序 插入排序是一种简单直观的排序算法其核心思想是将未排序的元素逐个插入到已排序的序列中以便生成一个新的有序序列。插入排序的过程类似于打扑克牌时的整理牌的方法即将一张牌插入到已经排好序的牌中的适当位置。
插入排序的基本思路是从第二个元素开始逐个将元素插入到前面已经排好序的子序列中。具体而言对于第 i 个元素我们将其与前面的元素逐个比较找到第一个比它小的元素然后将它插入到这个元素后面即可保证前 i 个元素已经排好序。这个过程不断重复直到整个序列都有序为止。
插入排序的时间复杂度为 O(n^2)它的性能与输入数据的初始顺序有关。如果输入数据已经接近有序那么插入排序的效率会比较高因为它只需要进行少量的比较和移动操作。但如果输入数据的顺序比较随机那么插入排序的效率会比较低因为它需要进行大量的比较和移动操作。 // 插入排序
void InsertSort(int* a, int n)
{//从第2个元素开始插入排序for (int i 1; i n; i){int end i - 1; // 已排序序列的最后一个元素的下标int tmp a[i]; // 待插入的元素//将待插入的元素与已排序的元素从后往前依次比较while (end 0){if (tmp a[end]){a[end 1] a[end]; // 如果比已排序的元素小则将已排序的元素后移一位end--;}else{break; // 如果找到一个比待插入元素小的位置则退出循环}}a[end 1] tmp; // 将待插入的元素插入到已排序的序列中}
}3.希尔排序 希尔排序Shell Sort是插入排序的一种改进版本也称为缩小增量排序diminishing increment sort。它通过将待排序的序列分割成若干个子序列对每个子序列进行插入排序从而实现对整个序列的排序。
希尔排序的核心思想是将相距某个“增量”的元素组成一个子序列对每个子序列进行插入排序使得整个序列在增量不断缩小的情况下逐步变得有序。最后当增量为1时整个序列就变成了一个有序序列。
具体实现中希尔排序先将待排序的元素按照一定的增量分成若干个子序列对每个子序列进行插入排序。然后逐渐减小增量继续对子序列进行插入排序直到增量为1时完成最后一次排序整个序列就变成了有序序列。
希尔排序的时间复杂度为 O(n log n) 到 O(n^2)具体取决于增量的选择和子序列的划分方式。希尔排序的优点是它的实现比较简单只需要对插入排序进行一些改进即可。缺点是增量序列的选择比较困难不同的增量序列对性能的影响也比较大。
//希尔排序
void ShellSort(int* a, int n)
{int gap n;while (gap 1){gap / 2;for (int i 0; i n - gap; i){int end i;int tmp a[i gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}
}4.简单选择排序 选择排序Selection Sort是一种简单直观的排序算法其核心思想是在未排序序列中选择最小或最大的元素放到已排序序列的末尾直到所有元素都排完为止。
具体实现中选择排序从未排序序列中找到最小或最大的元素然后将它与未排序序列的第一个元素交换这样就可以把该元素放到已排序序列的末尾。然后在剩余的未排序序列中继续找到最小或最大的元素重复上述操作直到所有元素都排完为止。
选择排序的时间复杂度为 O(n^2)它的性能比冒泡排序略好但比插入排序差。选择排序的优点是它的实现比较简单只需要进行 n-1 次比较和 n 次交换因此在某些情况下它的性能可能比其他排序算法更好。缺点是它的时间复杂度比较高不适合对大规模数据进行排序。
方法1双向遍历选择排序
//交换
Swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}
void SelectSort1(int* a, int n)
{int left 0;int right n - 1;while (left right){int max left, mini left;for (int i left 1; i right; i){if (a[i] a[mini]){mini i;}if (a[i] a[max]){max i;}}Swap(a[left], a[mini]);if (left max){max mini;}Swap(a[right], a[max]);left;--right;}
}方法2单向遍历选择排序
//交换
void Swap(int* a, int* b)
{int temp *a;*a *b;*b temp;
}void SelectSort2(int* a, int n)
{int min,i,j;for (int i 0; i n - 1; i){min i;for (int j i 1; j n; j){if (a[j] a[min]){min j;}}int temp a[min];a[min] a[i];a[i] temp;}
}5.归并排序 方法1递归
这是一种基于分治的排序算法 - 归并排序。 思路:
将数组分成两个子数组,递归调用排序子数组将两个有序子数组合并成一个有序数组
void _MergeSort(int* a, int begin, int end, int* tmp)
{if (beginend){return;}int mid (begin end) / 2;//[begin,mid] [mid1,end]子区间递归排序_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid 1, end, tmp);//[begin,mid] [mid1,end]归并int begin1 begin, end1 mid;int begin2 mid 1, end2 end;int i begin;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[i] a[begin1];}else{tmp[i] a[begin2];}}while (begin1 end1){tmp[i] a[begin1];}while (begin2 end2){tmp[i] a[begin2];}memcpy(a begin, tmp begin, sizeof(int) * (end - begin 1));
}
void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(mallco fail);return;}_MergeSort(a, 0, n - 1, tmp);free(tmp);
}方法2非递归
思路
使用一个gap进行划分,从1开始扩大gap,每次将相邻gap大小的两个子数组合并合并相邻gap大小的两个子数组的方法和递归版本是一样的每次将gap * 2,进行下一轮划分和合并重复此过程,直到gap n,排序完成
//非递归
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(mallco fail);return;}int gap 1;while (gapn){for (int i 0; i n; i 2 * gap){//[begin1,end1][begin2,end2]int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;if (end1 n || begin2 n){break;}if (end2 n){end2 n - 1;}int j i;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[j] a[begin1];}else{tmp[j] a[begin2];}}while (begin1 end1){tmp[j] a[begin1];}while (begin2 end2){tmp[j] a[begin2];}//归并一部分拷贝一部分memcpy(a i, tmp i, sizeof(int) * (end2 - i 1));}gap * 2;}free(tmp);
}6.快速排序 方法1随机取keyi
思路
选择一个基准元素(使用随机数随机选择一个元素)将所有比基准元素小的元素移动到其左边,所有比基准元素大的元素移动到其右边对基准元素的左右两边重复第一步和第二步,直到全部排序完成
void Swap(int* p1, int* p2)
{int temp *p1;*p1 *p2;*p2 temp;
}
void QuickSort(int* a, int left, int right)
{if (left right)return;int begin left;int end right;//随机选keyint randi left (rand() % (right - left));Swap(a[left], a[randi]);int keyi left;while (left right){//右边找小while (left right a[right] a[keyi])--right;//左边找大while (leftright a[left]a[keyi])left;Swap(a[left], a[right]);}
}
方法2三数取中
思路
首先利用中位数作为基准值,选择最稳定的基准值。获取三个数的中位数: 如果a[left]a[mid],那么如果a[mid]a[right], mid是中位数否则比较a[left] 和 a[right],较大值是中位数将中位数与第一个元素交换,作为基准值其他部分与普通快速排序相同
void Swap(int* p1, int* p2)
{int temp *p1;*p1 *p2;*p2 temp;
}
int GetMidNumi(int* a, int left, int right)
{int mid (left right) / 2;if (a[left] a[mid]){if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return left;} else{return right;}}else//a[left]a[mid]{if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return left;}else{return right;}}
}
void QuickSort2(int* a, int left, int right)
{if (left right)return;int begin left;int end right;int midi GetMidNumi(a, left, right);if (midi ! left){Swap(a[midi], a[left]);}int keyi left;while (left right){//右边找小while (left right a[right] a[keyi])--right;//左边找大while (leftright a[left]a[keyi])left;Swap(a[left], a[right]);}Swap(a[keyi], a[left]);keyi left;QuickSort2(a, begin, keyi - 1);QuickSort2(a, keyi 1, end);
}方法3挖坑法 思路
使用 begin 和 end 表示子数组范围key 记录基准值,hole 记录待填充位置把 left 和 right 指针分别指向 begin 和 endwhile 循环右边第一个小于等于 key 的元素,记录其索引到 hole, right左边第一个大于 key 的元素,记录其索引到 hole,lefthole 位置填充 key 值对基准值左右两侧的子数组递归调用快速排序
void QuickSort3(int* a, int left, int right)
{if (left right)return;int begin left;int end right;int key a[left];int hole left;while (left right){//右边找小while (left right a[right] key)--right;a[hole] a[right];hole right;//左边找大while (left right a[left] key)left;a[hole] a[left];hole left;}a[hole] key;QuickSort3(a, begin, hole - 1);QuickSort3(a, hole 1, end);
}方法4前后指针法 快速排序的前后指针法也称为双指针法是一种常见的划分方式。它的基本思想是将整个序列分为小于等于主元的左半部分和大于主元的右半部分然后递归地对左右两个部分进行排序。
思路
依然使用left、right指针和基准值pivot。额外引入一个prev指针,记录小于pivot的最后一个元素的位置。当遍历到一个元素时如果元素 pivot,将其与prev指向的元素交换,prev后移 1 位如果元素 pivot,直接略过如果元素 pivot,继续遍历最终prev指向的位置,就是pivot的正确位置。
int QuickSort4(int* a, int left, int right)
{int midi GetMidNumi(a, left, right);if (midi ! left){Swap(a[midi], a[left]);}int keyi left;int prev left;int cur left 1;while (cur right){if (a[cur] a[keyi] prev ! cur)Swap(a[cur], a[prev]);cur;}Swap(a[prev], a[keyi]);keyi prev;return keyi;
}方法5:非递归
这里使用了一个栈来模拟递归过程。首先将整个序列的左右端点入栈之后每次取出栈顶的左右端点进行一次划分并将新的左右端点入栈直到栈为空为止。在划分函数中使用双指针法将小于等于主元的元素放在左边大于主元的元素放在右边最后把主元放在中间并返回主元的下标。
需要注意的是这里使用了一个结构体 Range 来表示左右端点的范围这样可以方便地把左右端点打包在一起并压入栈中。
#include stdio.h
#define MAX_SIZE 100
typedef struct {int l;int r;
} Range;void swap(int* a, int* b) {int temp *a;*a *b;*b temp;
}int partition(int arr[], int l, int r) {int pivot arr[l];while (l r) {while (l r arr[r] pivot) r--;arr[l] arr[r];while (l r arr[l] pivot) l;arr[r] arr[l];}arr[l] pivot;return l;
}void quickSort(int arr[], int n) {Range stack[MAX_SIZE];int top -1;stack[top] (Range){ 0, n - 1 };while (top 0) {Range range stack[top--];if (range.l range.r) continue;int p partition(arr, range.l, range.r);stack[top] (Range){ range.l, p - 1 };stack[top] (Range){ p 1, range.r };}
}int main() {int arr[] { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };int n sizeof(arr) / sizeof(arr[0]);quickSort(arr, n);for (int i 0; i n; i) {printf(%d , arr[i]);}printf(\n);return 0;
}方法6三路划分 思路
跟key相等的值往后推比key小的甩到左边比key大的甩到右边跟key相等的就在中间
void swap(int* a, int* b) {int temp *a;*a *b;*b temp;
}
void quicksort(int arr[], int low, int high) {if (low high) {return;}// 选取第一个元素为基准值int pivot arr[low];// lt指向小于基准值的部分的最后一个元素int lt low;// gt指向大于基准值的部分的第一个元素int gt high;// i指向当前处理的元素int i low 1;// 三路划分while (i gt) {if (arr[i] pivot) {// 将小于基准值的元素交换到lt部分swap(arr[i], arr[lt]);lt;i;}else if (arr[i] pivot) {// 将大于基准值的元素交换到gt部分swap(arr[i], arr[gt]);gt--;}else {// 相等的元素直接跳过i;}}// 递归排序小于基准值的部分quicksort(arr, low, lt - 1);// 递归排序大于基准值的部分quicksort(arr, gt 1, high);
}
int main() {int arr[] {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};int n sizeof(arr) / sizeof(arr[0]);quicksort(arr, 0,n-1);for (int i 0; i n; i) {printf(%d , arr[i]);}printf(\n);return 0;
}7.堆排序 思路
使用 maxHeapify() 函数维护最大堆的属性。
使用 n/2 - 1 作为起始索引,逐层地将数组调整为最大堆。
排序部分:
将堆顶元素(最大元素)与末尾元素交换缩小堆的范围(n范围减1),再次调用 maxHeapify() 函数,维护最大堆的属性。重复上两步,直到堆范围为0。
// 交换函数
void swap(int* a, int* b) {int temp *a;*a *b;*b temp;
}void maxHeapify(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) {swap(arr[i], arr[largest]);maxHeapify(arr, n, largest);}
}void heapSort(int arr[], int n) {// 构建最大堆for (int i n / 2 - 1; i 0; i--)maxHeapify(arr, n, i);// 排序for (int i n - 1; i 0; i--) {swap(arr[0], arr[i]); // 将最大值交换到数组末尾maxHeapify(arr, i, 0);}
}int main() {int arr[] { 12, 11, 13, 5, 6, 7 };int n sizeof(arr) / sizeof(arr[0]);heapSort(arr, n);// 打印排序后的数组for (int i 0; i n; i)printf(%d , arr[i]);return 0;
}8.计数排序 思路
扫描一次给定的数组,找到最大元素和最小元素根据最大元素和最小元素,计算出需要多大的空间用于排序创建计数数组 countA,长度为范围(max - min 1)遍历给定数组,对于每个元素 a[i],计数数组 countA[a[i] - min] 加 1对计数数组进行累加求和,使每个元素表示当前元素及之前所有元素的个数遍历给定数组,将元素放在正确位置上
#includestdio.h
#includestring.h
#includestdlib.h
void CountSort(int* a, int n)
{int max a[0], min a[0];for (int i 1; i n; i){if (a[i] max){max a[i];}if (a[i] min){min a[i];}}int range max - min 1;int* countA (int*)malloc(sizeof(int) * range);if (countA NULL){perror(malloc fail);return;}memset(countA, 0, sizeof(int) * range);//计数for (int i 0; i n; i){countA[a[i] - min];}//排序int j 0;for (int i 0; i range; i){while (countA[i]--){a[j] i min;}}free(countA);
}
int main()
{int arr[] { 2,3,5,6,7,3,2,5,5,5,9,200 };int sz sizeof(arr) / sizeof(arr[0]);CountSort(arr, sz);for (int i 0; i sz; i){printf(%d , arr[i]);}return 0;
}9.基数排序 思路
对数组按照最低阶(个位数)进行分配,然后收集。再按照次低阶(十位数)分配和收集,依次类推到最高阶。每次分配、收集都会让数组更加有序。
具体实现
定义最大基数为 RADIX(10),一个辅助队列组 Q[]Getkey() 函数获取元素 value 在指定位数 k 的值Distribute() 函数将数组中元素按照 k 位分配到相应的队列中Collect() 函数收集队列中的元素,反向填充数组RadixSort() 函数依次分配、收集 K次,K为指定位数
#includeiostream
#includestdio.h
#includequeue
using namespace std;
#define K 3
#define RADIX 10
queueint Q[RADIX];int Getkey(int value, int k)
{int key 0;while (k 0){key value % 10;value / 10;k--;}return key;
}
//分发数据
void Distribute(int arr[], int left, int right, int k)
{for (int i left; i right; i){int key Getkey(arr[i],k);Q[key].push(arr[i]);}
}
//回收数据
void Collect(int arr[])
{int k 0;for (int i 0; i RADIX; i){while (!Q[i].empty()){arr[k] Q[i].front();Q[i].pop();}}
}
void RadixSort(int* arr, int left, int right)
{for (int i 0; i K; i){//分发数据Distribute(arr, left, right, i);//回收数据Collect(arr);}
}int main()
{int arr[] { 278,109,63,930,589,184,505,269,8,83 };int sz sizeof(arr) / sizeof(arr[0]);for (int i 0; i sz; i){printf(%d , arr[i]);}printf(\n);//基数排序RadixSort(arr, 0, sz);for (int i 0; i sz; i){printf(%d , arr[i]);}return 0;
}9.桶排序 桶排序是一种线性排序算法它的基本思想是将待排序的元素分到不同的桶中每个桶内的元素再分别使用其他排序算法进行排序最后合并所有桶中的元素即可得到有序序列。桶排序的时间复杂度为 O(n)但是它的空间复杂度较高需要额外的空间来存储桶。
#include stdio.h
#include stdlib.h// 桶排序
void bucket_sort(int arr[], int n) {int max_num arr[0];int min_num arr[0];int i, j, k;for (i 1; i n; i) {if (arr[i] max_num) {max_num arr[i];}if (arr[i] min_num) {min_num arr[i];}}int bucket_size (max_num - min_num) / n 1;int bucket_count (max_num - min_num) / bucket_size 1;int **buckets malloc(sizeof(int*) * bucket_count);for (i 0; i bucket_count; i) {buckets[i] malloc(sizeof(int) * n);}int *count malloc(sizeof(int) * bucket_count);for (i 0; i bucket_count; i) {count[i] 0;}for (i 0; i n; i) {int index (arr[i] - min_num) / bucket_size;buckets[index][count[index]] arr[i];count[index];}k 0;for (i 0; i bucket_count; i) {for (j 0; j count[i]; j) {arr[k] buckets[i][j];k;}}for (i 0; i bucket_count; i) {free(buckets[i]);}free(buckets);free(count);
}// 测试桶排序
int main() {int arr[] {5, 2, 8, 3, 9, 6};int n sizeof(arr) / sizeof(int);bucket_sort(arr, n);printf(排序后的结果为);for (int i 0; i n; i) {printf(%d , arr[i]);}printf(\n);return 0;
}
