建站之星破解版下载,承德网站,微擎pc网站开发,化妆品网站建设思路排序 下面的代码会用到宏定义#xff0c;因为再C中没有swap交换函数#xff0c;所以对于swap的宏定义代码如下#xff1a; #define swap(a, b) {\__typeof(a) __a a; a b; b __a;\
} 稳定排序#xff1a; 1.插入排序#xff1a; 插入排序会将数组#xff0c;分位两个部… 排序 下面的代码会用到宏定义因为再C中没有swap交换函数所以对于swap的宏定义代码如下 #define swap(a, b) {\__typeof(a) __a a; a b; b __a;\
} 稳定排序 1.插入排序 插入排序会将数组分位两个部分一般分为前后两部分而前半部分为已排序区后半部分为未排序区插入排序的操作就是把未排序区中的元素插入到已排序区中的去并且满足排序区的单调性如图下面的操作实现一个单调递增序列 数组的原本样子现在使位置0是已排序区先去从位置1开始去插入 将12插入到23前面使位置01形成单调递增 进行插入对位置2插入发现不用插入直接对下一个位置进行插入 位置4也不用进行插入保持原位置对位置5进行插入 最后完成排序 时间复杂度 代码实现 void insert_sort(int *arr, int n) {//arr排序数组n数组长度for (int i 1; i n; i) {//位置0开始定为已排序区for (int j i; j 1 arr[j] arr[j - 1]; j--) {//将位置i进行插入到前面的以排序区swap(arr[j], arr[j - 1]);//交换位置}}return ;
} 2.冒泡排序 冒泡排序为什么会叫冒泡排序假如实现单调递增序列那么每一次都会将未排序中的最大的元素放到未排序区中的最后去把数组立起来数组的最后的位置在上那么是不是每次未排序的最大元素会像冒泡一样往上升所以叫冒泡排序 如图数组最开始状态 第一次冒泡 第一次完冒泡后最大的元素已经放到了数组最后位置也相当于放到了已排序区中了然后这样一直循环直到排完序 时间复杂度 代码实现 做了一个小小的优化 void bubble_sort(int *arr, int n) {int time 1;//用来标记这次循环是否发生了冒泡交换for (int i 1; i n time; i) {//如果没有发生交换说明数组已经排好了序time 0;for (int j 0; j n - i; j) {if (arr[j] arr[j 1]) {swap(arr[j], arr[j 1]);time;}}}return ;
} 3.归并排序 将一个数组从中间分开然后通过递归一直将子数组进行分开直到数组只有两个元素然后通过回溯的过程中进行排序然后一直回溯到整个数组并拢完成排序 如图将数组这样二分下去 然后从下往上进行排序单调递增 合并排序 合并在排序 最终完成排序 时间复杂度 代码实现 这个过程比较容易理解就是代码实现有那么一点复杂来看代码 void merge_sort(int *arr, int l, int r) {//数组的头位置r数组的末尾在if (r - l 1) {//当分到只有2个元素和1个元素时递归出口if (r - l 1 arr[l] arr[r]) {//两个元素进行排序swap(arr[l], arr[r]);}return ;}int mid (l r) 1;//开始分列merge_sort(arr, l, mid);//递归左边数组merge_sort(arr, mid 1, r);//递归右边数组int *temp (int *)malloc(sizeof(int) * (r - l 1));//创建一个空间来存子数组的元素int p1 l, p2 mid 1, k 0;//p1数组分裂开的前部分的起始坐标,p2数组分裂开后半部分的起始坐标while (p1 mid || p2 r) {if (p2 r || (p1 mid arr[p1] arr[p2])) temp[k] arr[p1];else temp[k] arr[p2];}memcpy(arr l, temp, sizeof(int) * (r - l 1));//将排好序的子数组拷贝给原数组free(temp);return ;
} 4.基数排序 这里假设数组都是两位数先对数组进行元素的个位进行排序然后在对数组的十位进行排序这样就能对数组拍好序如果位数不相同取位数最大的数进行位数排序假如最大的位数是3位那么就进行3次位数排序如果位数10位那就进行10次位数排序 如图数组最初 进行个位排序上面的表格就是对于个位数的统计对于排序时会起到作用 在进行10位排序 最终完成排序 时间复杂度 代码实现 void number_sort(int *arr, int n, int exp) {int count[10] {0};for (int i 0; i n; i) {count[arr[i] / exp % 10] 1;//对每位数的数的个数统计}for (int i 1; i 10; i) {count[i] count[i - 1];//位数排序从小到大现在的操作就是使count变为下标}int *sum (int *)malloc(sizeof(int) * n);for (int i n - 1; i 0; i--) {//假如个位已近排序后那么个位大的在后而根据十位排序也是从高位排到低位所以需要倒过来存sum[count[arr[i] / exp % 10] - 1] arr[i];//下标从0开始所以需要-1count[arr[i] / exp % 10]--;//对应的位数已经排序一个所以数量-1}memcpy(arr, sum, sizeof(int) * n);free(sum);return ;
}void radix_sort(int *arr, int n) {int max INT_MIN;for (int i 0; i n; i) {//获取最大数的数max max arr[i] ? max : arr[i];}for (int i 1; max / i 0; i * 10) {//从个位一直到大于最大数的位数number_sort(arr, n, i);}return ;
} 非稳定排序 1.选择排序 将数组分为两个区域一个已排序区和一个未排序区每次将未排序区中的最值放在已排序区中 如图将54放放到最后也就是已排序区中 这样一直在未排序区中选择直到排序完成 时间复杂度: 代码实现 void select_sort(int *arr, int n) {//这里实现的是将最小的元素放在最前面现在前面就是已排序区for (int i 0; i n - 1; i) {int ind i;//ind先记录当前准备排序的位置for (int j i 1; j n; j) {if (arr[ind] arr[j]) ind j;//ind记录未排序区中最小值的值的位置}swap(arr[ind], arr[i]);//将未排序的区的最小值放在准备排序的位置}return ;
} 2.快速排序 选择数组头步位置作为基数用一个变量记录下来然后将这个基数作为中间值将数组分为两个部分前半部分小于这个基数后半部分大于基数然后在对两个部分进行上面的操作直接这两个部分不能再分这里不一定是二分开的有可能这个基数是最大值那么就没有前半部分 如图数组初始状态 将32作为基数把数组分为两部分分 然后再对左边部分进行快排右边部分进行快排 这里只是刚好不用变化然后继续上面的操作直到最后排完序 完成排序。 时间复杂度 最坏 代码实现 //l最初为0r最初为n-1
void quick_sort(int *arr, int l, int r) {if (r l) return ;int x l, y r, num arr[l];while (x y) {while (x y arr[y] num) y--;//如果大于基数的部分该位置数大于基数就不用交换if (x y) arr[x] arr[y];//如果xy说明y位置的值是小于基数的就放到前面去第一次的时候x的位置就是基数的位置所以覆盖的是基数的位置while (x y arr[x] num) x;//如果小于基数的部分该位置数小于等于基数就不用交换if (x y) arr[y--] arr[x];//xy,说明x位置的值是小于基数的现在y位置是之前小于基数的位置直接覆盖}arr[x] num;//将基数放到分割位置quick_sort(arr, l, x - 1);//小于基数的部分quick_sort(arr, x 1, r);//大于基数的部分return ;
} 3.希尔排序 希尔排序其实就是对于选择排序的一个优化的算法而最最坏的情况就是降为一个普通的选择排序。 选择一个移动的长度最开始选择数组长度的1/2然后一直除2直到步长等于1进行一次插入排序这个步长的作用就是从一个位置往前移动多少步进行对该位置的值进行比较如果不满住单调性就进行交换然后交换如果还能往前目前的步长长度继续往前比较 如图直接上图片理解 现在的步长选作4那么就从位置4进行开始排序 他俩进行比较然后数组是单调递增就就需要交换然后比较位置向后移动 然后第一次步长结束后那么步长在除以2 然后再次进行比较 继续往后 这里发生了交换而且现在的位置还能往前走步长所以也需要比较 比较后不用发生交换继续刚刚的位置往后 这里发生了交换又需要往前走 直到不能发生交换然后现在走到了最后的位置进行步数除以2等于1进行一次选择排序 这里发生了交换那就需要再往前走步长那么长进行比较 最后遍历没有发生交换并且步长为除2等于0了完成排序 时间复杂度 最坏 代码实现 void shell_sort(int *arr, int n) {int step;for (step n / 2; step 0; step 1) {//步长循环for (int i step; i n; i) {//从步长长度开始往后循环for (int j i; j step arr[j] arr[j - step]; j - step) {//如果不满足单调性发生交换并且如果现在的位置长度大于等于步长继续往前移动进行比较swap(arr[j], arr[j - step]);}}}return ;
} 4.堆排序 堆堆排序在前面这个链接的文章里因为单独将堆排序有那么一点难理解需要结合对堆的理解才容易一些
