排序算法C++

冒泡排序快速排序归并排序简单选择排序堆排序直接插入排序希尔排序基数排序记面试常问简单阐述一下快速排序归并排序的过程。交换排序快速排序从数组中选择一个元素作为中轴元素然后把数组中所有小于中轴元素的元素放在其左边所有大于或等于中轴元素的元素放在其右边。此时中轴元素所处的位置的是有序的。我们无需再移动中轴元素的位置。从中轴元素开始把大的数组切割成两个小的数组(两个数组都不包含中轴元素)接着通过递归的方式让中轴元素左边的数组和右边的数组也重复同样的操作直到数组的大小为1此时每个元素都处于有序的位置。步骤如下选取第一个数为基准或随机值为基准值将比基准小的数交换到前面比基准大的数交换到后面对左右区间重复第二步直到各区间只有一个数快速排序其实是一种分治算法即分而治之。大规模的问题分解成若干个规模较小的相同子问题。通过一组排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据小然后再按此方法对这两部分数据进行快速排序整个排序过程递归进行以此使所有数据变成有序序列。#includeiostream #includevector #includealgorithm #includemath.h #includeutility using namespace std; void swap(int*a,int*b) { /*int tmp 0; tmp *a;*/ int tmp *a; *a *b; *b tmp; } int random(vectorint nums, int left, int right) { int posrand() % (right - left 1) left; swap(nums[left], nums[pos]); // 把随机基准换到最左边 return left; // 基准现在在 left 位置 } int partition(vectorint nums, int left, int right) { int i left; int j right; int pivotPos random(nums, left, right); while (i j) { while (i j nums[j] nums[pivotPos]) { j--; } while (i j nums[i] nums[pivotPos]) { i; } swap(nums[i], nums[j]); } swap(nums[pivotPos], nums[i]); return i; } void quickSort(vectorint nums, int left, int right) { if (left right) return; int pivot partition(nums, left, right); quickSort(nums, left, pivot - 1); quickSort(nums,pivot 1,right); } int main() { vectorint nums { 3, 1, 4, 1, 5, 9, 2, 6 }; quickSort(nums, 0, nums.size() - 1); for (int x : nums) { cout x ; } return 0; }以上随机基准必须先交换到left位置否则双指针移动时会把基准值覆盖掉分区直接失效。void swap(vectorint nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; }#includeiostream #includevector #includealgorithm #includemath.h #includeutility using namespace std; void swap(int*a,int*b) { /*int tmp 0; tmp *a;*/ int tmp *a; *a *b; *b tmp; } int partition(vectorint nums, int left, int right) { int i left; int j right; while (i j) { while (i j nums[j] nums[left]) { j--; } while (i j nums[i] nums[left]) { i; } swap(nums[i], nums[j]); } swap(nums[left], nums[i]);//最后把基准数换到中间 return i; } void quickSort(vectorint nums, int left, int right) { if (left right) return; int pivot partition(nums, left, right); quickSort(nums, left, pivot - 1); quickSort(nums,pivot 1,right); } int main() { vectorint nums { 3, 1, 4, 1, 5, 9, 2, 6 }; quickSort(nums, 0, nums.size() - 1); for (int x : nums) { cout x ; } return 0; }int i rand() % (r - l 1) l; //选取基准值的另外方法以上是双指针只是将随机的第一个值作为基准值极端情况下会退化成冒泡排序。核心问题在于基准值选的不好如果选取的值恰好是当前序列中最小或最大值也就是时间复杂度最坏情况。所以最好选用左中右中位数作为基准值避免划分位置不好的情况。最好情况是每次划分选择的中间数恰好将当前序列等分经过 log (n) 趟划分便可得到⻓度为 1 的⼦表 这样时间复杂度 O(nlogn)。最坏情况是每次所选中间数是当前序列中的最⼤或最⼩元素这使每次划分所得⼦表其中⼀个为空表 这样⻓度为 n 的数据表需要 n 趟划分整个排序时间复杂度 O(n²)。快速排序是对冒泡排序的⼀种改进不稳定。冒泡排序快速排序和冒泡排序都属于交换排序什么是交换排序所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排序特点将键值较大的记录向序列尾部移动键值较小的记录向序列的前部移动。。基本思想就是通过相邻元素的比较和交换来将最大或最小的元素逐步“冒泡”到数组的末尾。遍历数组比较相邻的两个元素如果前一个元素大于后一个元素则交换它们的位置使较大的元素“冒泡”到后面。继续遍历数组重复上述比较和交换的过程直到最后一个元素。重复上述步骤每次遍历时减少一个元素直到所有元素都排好序。void swap(int* a, int* b) { int temp *a; *a *b; *b temp; } void bubbleSort(int* arr, int n) { //2.再写多趟 for (int j 0; j n; j) { bool exchange false; //1.先写一趟 for (int i 0; i n - 1 - j;i) { if (arr[i] arr[i 1]) { swap(arr[i], arr[i 1]); exchange true; } } if (exchange false) return; } }cpp #include iostream using namespace std; 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; } } } } int main() { int arr[] {64, 34, 25, 12, 22, 11, 90}; int n sizeof(arr) / sizeof(arr[0]); bubbleSort(arr, n); cout 排序后的数组; for (int i 0; i n; i) { cout arr[i] ; } return 0; } 冒泡排序虽然简单但是它的时间复杂度较高最差为O(n^2)不适用于大规模数据的排序。在实际应用中更常用的是更高效的排序算法如快速排序、归并排序等。最好的时间复杂度On。归并排序归并排序是建立在归并操作上的一种有效的排序算法采用分治法的一个典型应用。快排也是分治将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。归并分割的意义把整个数组分割为以个为单位。#includeiostream #includevector using namespace std; //合并两个有序数组 void merge(vectorint arr, int left, int middle, int right) { //创建两个临时数组用于存储分割后的数组 int n1 middle - left 1;//左边数组大小 int n2 right - middle;//右边数组大小 vectorint temp1(n1); vectorint temp2(n2); //分别将原数组中的元素拷贝到临时数组中 for (int i 0; i n1; i) { temp1[i] arr[left i]; } for (int j 0; j n2; j) { temp2[j] arr[middle1j]; } //合并两个临时数组到原数组中 int i 0; int j 0;//右边数组起始索引 int k left;//合并后数组的起始索引 while (i n1 j n2) { if (temp1[i] temp2[j]) { arr[k] temp1[i]; i; } else { arr[k] temp2[j]; j; } k; } //将剩余元素拷贝到原数组中 while (i n1) { arr[k] temp1[i]; i; k; } while (j n2) { arr[k] temp2[j]; j; k; } } void mergeSort(vectorint arr, int left, int right) { if (left right) { int middle left (right - left) / 2; //分割数组并递归调用归并排序 mergeSort(arr, left, middle); mergeSort(arr, middle 1, right); //合并两个有序数组 merge(arr, left, middle, right); } } int main() { vectorint arr { 9, 5, 7, 3, 1, 8, 6, 2, 4 }; int n arr.size(); cout 原始数组: ; for (int i 0; i n; i) { cout arr[i] ; } cout endl; // 调用归并排序算法 mergeSort(arr, 0, n - 1); cout 排序后的数组: ; for (int i 0; i n; i) { cout arr[i] ; } cout endl; return 0; }这样也行if (L R)return;//递归结束条件 int mid (R - L) / 2 L;//求中位数 Merg_Sort(vec, L, mid);//递归分解左边 Merg_Sort(vec, mid 1, R);//递归分解右边 //合并两个有序数组 Merg(vec, L, mid, R);插入排序直接插入排序直接插入排序的步骤如下从第一个元素开始该元素可以认为已经被排序。取出下一个元素在已排序的元素序列中从后向前扫描。如果该元素已排序大于新元素将该元素移到下一位置。重复步骤3直到找到已排序的元素小于或者等于新元素的位置。将新元素插入到该位置后。重复步骤2~5直到所有元素都已排序。对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。void InsertSort(int arr[], int l) { int temp; int j; for (int i 1; i l; i) { if (arr[i] arr[i - 1]) { temp arr[i]; for (j i-1; j 0temparr[j]; j--) { arr[j 1] arr[j]; } arr[j 1] temp;//这里j多后退了一步。。 } }for (int k 0; k l; k) { cout arr[k] ; }cout endl; }直接插入排序的时间复杂度最坏情况下为O(N^2)此时待排序列为逆序或者说接近逆序直接插入排序的时间复杂度最好情况下为O(N)此时待排序列为升序或者说接近升序希尔排序希尔排序是按其设计者希尔的名字命名的。希尔就想若是能先将待排序列进行一次预排序使待排序列接近有序接近我们想要的顺序然后再对该序列进行一次直接插入排序此时已经排好序了并且时间复杂度也降低了即希尔排序 预排序 一次直接插入排序插入排序算法的一种改进版本可以减少插入排序算法中数据移动的次数加快排序速度因此也叫缩小增量排序。希尔排序算法的基本思想是将原始数据分成特定间隔的几组数据然后使用插入排序算法对每组数据进行排序排序后再减少间隔距离重复上面的步骤直到排序完成为止。首先选择一个增量序列通常选择增量序列gap为n/2n/4n/8...1其中n为数组的长度根据增量序列将数组分成若干个子序列对每个子序列进行插入排序逐渐缩小增量序列重复步骤2直到增量为1即对整个数组进行一次插入排序为什么要让gap由大到小gap越大数据挪动得越快gap越小数据挪动得越慢前期让gap较大可以让数据更快得移动到自己对应的位置附近减少挪动次数一般情况下取序列的一半作为增量然后依次减半直到增量为1也可自己设置void ShellSort(int* a, int n) { int gap n; // gap 1时是预排序目的让他接近有序 // gap 1是直接插入排序目的是让他有序 while (gap1) { gap gap / 3 1;//也可以写成gap/2.目的都是为了最后一次gap一定要为1. for (int i 0; i n - gap; i) { int end i; int tmp a[end gap]; while (end 0) { if (a[end] tmp) { a[end gap] a[end]; end - gap; } else { break; } a[end gap] tmp; } } } }可能写起来比较麻烦都是希尔排序的效率可是非常高度。它的效率略低于但接近快排和堆排远高于插入排序插入排序的效率又远高于冒泡排序。https://blog.csdn.net/2303_79015671/article/details/134796935?fromshareblogdetailsharetypeblogdetailsharerId134796935sharereferPCsharesource2401_82607598sharefromfrom_link选择排序简单选择排序简单选择排序过程中每次选取当前元素最小的元素,依次进行下去即和第一个元素交换依次进行交换直到剩余一个元素此时整个序列已经有序每一趟简单选择排序可确定一个元素的最终位置。按顺序每次取出剩下数组段的最小值放在最前面。/*简单选择排序递增*/ void SelectSort1(int r[],int n) { int i,j,min,temp; for(i0; in-1; i) { //for循环进行n-1趟 mini; //min变量记录最小元素的位置 for(ji1; jn; j) { //从无序序列中选择一个最小的元素 if(r[j]r[min]) minj; } tempr[i]; //将最小元素与无序序列的第一个关键字进行交换 r[i]r[min]; r[min]temp; } }同样的递减的/*简单选择排序递减*/ void SelectSort2(int r[],int n) { int i,j,max,temp; for(i0; in-1; i) { //for循环进行n-1趟 maxi; //max变量记录最小元素的位置 for(ji1; jn; j) { //从无序序列中选择一个最大的元素 if(r[j]r[max]) maxj; } tempr[i]; //将最大元素与无序序列的第一个关键字进行交换 r[i]r[max]; r[max]temp; } }堆排序大、小根堆堆排序是利用堆树来进行排序可以将其视为一棵完全二叉树树中每一个结点均大于或等于其两个子结点的值根结点是堆树中的最小值或最大值即对应小根堆和大根堆。基于小根堆得到的序列为递减序列基于大根堆得到的序列为递增序列。调整堆的代码/*堆调整*/ void Adjust(int r[],int low,int high) { int ilow,j2*i; //r[j]是r[i]的左孩子结点 int tempr[i]; while(jhigh) { if(jhighr[j]r[j1]) //若当前结点的右孩子较大则将j指向右孩子 j; if(tempr[j]) { r[i]r[j]; //将r[j]调整至双亲结点的位置上互换 ij; //修改i和j的值以便继续调整 j2*i; } else break; //调整结束 } r[i]temp; //将被调整的结点放到其应当的位置 }在建立根堆后将堆中堆顶元素与堆的最后一个元素进行交换堆顶元素进入有序序列到达最终位置从无序序列中被排出符合选择排序的过程然后对剩下的无序序列继续进行调整依次进行下去……直到无序序列中剩余最后一个元素此时整个序列已经有序堆排序结束。 堆排序的代码如下/*堆排序*/ void HeapSort(int r[],int n){ int i,temp; for(in/2;i1;i--) //建立初始堆 Adjust(r,i,n); for(in;i1;i--){ //进行n-1次循环完成堆排序 tempr[1]; //将堆中最后一个元素与堆顶元素交换将其放入最终位置 r[1]r[i]; r[i]temp; Adjust(r,1,i-1); //对剩下的无序序列进行调整 } }基数排序基数排序是一种非比较型整数排序算法其原理是将众多数字按位分隔后进行排序。将所有待比较的数字正整数统一为同一长度位数不够的数字前面补0按照从个位十位百位······从低到高的顺序进行排序完成从低位到高位的排序后待排序数字也就完成了排序初始化 序列num{57 123 564 32 0 56 169 5 23 11 100}将上述序列的数字按照个位数字进行排序个位数字取值范围0-9我们可以将其设置为数组用来存储 序列中的数字如下所示然后我们将这些数字按照个位再取出来得到新的序列num_new{0 100 11 32123 23 564 5 56 57 169}下面按照十位百位继续进行排序结束后便是有序数列 动态效果示意图如下#include iostream #include vector using namespace std; int MaxBit(vectorint input) //求出数组中最大数的位数 { int max_num input[0]; //默认最大数为第一个数字 for (int i 0; i input.size(); i) //找出数组中的最大数 { if (input[i] max_num) { max_num input[i]; } } int p 0; while (max_num 0) { p; max_num / 10; //每次除以10取整即可去掉最低位 } return p; } int GetNum(int num, int d) //取出所给数字的第d位数字 { int p 1; while (d - 1 0) { p * 10; d--; } return num / p % 10; } vectorint RadixSort(vectorint input, int length) //基数排序 { vectorint bucket(length); //创建临时存放排序过程中的数据 vectorint count(10); //创建按位计数的技术容器即记录排序中按个位、十位...各个数的位置的个数 for (int d 1; d MaxBit(input); d) { // 计数器清0 for (int i 0; i 10; i) { count[i] 0; } // 统计各个桶中的个数 for (int i 0; i length; i) { count[GetNum(input[i], d)]; } for (int i 1; i 10; i) { //得到每个数应该放入bucket中的位置 count[i] count[i - 1]; } for (int i length - 1; i 0; i--) { //采用倒序进行排序是为了不打乱已经排好的顺序 int k GetNum(input[i], d); bucket[count[k] - 1] input[i]; count[k]--; } for (int j 0; j length; j) // 临时数组复制到 input 中 { input[j] bucket[j]; } } return input; } int main() { int arr[] { 50, 123, 543, 187, 49, 30, 0, 2, 11, 100 }; vectorint test(arr, arr sizeof(arr) / sizeof(arr[0])); cout 排序前:; for (int i 0; i test.size(); i) { cout test[i] ; } cout endl; vectorint result test; result RadixSort(result, result.size()); cout 排序后:; for (int i 0; i result.size(); i) { cout result[i] ; } cout endl; system(pause); }继续补充把。。。