鸡尾酒排序、计数排序"/>
排序算法01——冒泡排序、选择排序、鸡尾酒排序、计数排序
选择排序:
这边我先宏定义一个交换函数,下列这些排序都会用到,就可以直接引用了。
#define swap(a,b) {a+=b;b=a-b;a=a-b;}
选择排序算是非常简单入门的排序方法了。
直接贴代码了
void select(int arr[],int len)
{for (int i = 0; i < len-1; i++) //每循环一次找此次循环中的最大值 {int max = 0; //定义最大值下标为0for (int j =1;j<= len-i-1;j++) //区间[0,len-i-1]中 找到最大值 由于max的下标为0 所以j可以直接从1开始{if (arr[j]>arr[max]) //依次比较 大值下标放入max{max= j;}} if (max != len-i-1) //如果arr[max]不在最末尾 那么就放到最末尾{swap(arr[max],arr[len-i-1]);}} //每循环一次就会有一个最大值放到末尾 因此末尾的数都已经是有序的了 需要排序的数的就是0~len-i-1
}
时间复杂度为O(n^2)
那么能不能优化一下呢,当然可以。你看上述代码每一次循环,我们只找了一个最大值就继续下一次循环了,这实在是太浪费了。因此我们可以一次循环找到数组中的最大值和最小值,然后把最小值放前面,最大值放最后。这种操作就类似于鸡尾酒,上下一层层的。因此就叫做鸡尾酒排序。
鸡尾酒排序:
代码如下:
void cooktailsort(int arr[],int len)
{for (int i = 0; i < len/2; i++) //一次循环找两个值 所以循环次数减半{int min = i; int max = i; //将最大最小值下标都设为此次数组区间的最左值for (int j = i+1; j <= len-i-1; j++) //循环一次将最小值放到最前面 最大值放到最后面 因此区间为[i,len-1-i] { //max min 下标都为i j可以从i+1开始if (arr[j]>arr[max]){max = j;}if (arr[j]<arr[min]){min = j;}}if (min != i) //如果最小值下标不在区间最左 {swap(arr[min],arr[i]); //交换if (max == i) //如果一开始最大值在区间最左 那么交换后记得把最大值的下标也交换了 {max = min;}}if (max != len-i-1) //交换最大值与区间最右{swap(arr[max],arr[len-i-1]);}}
}
时间复杂度为O(n^2) 虽然时间复杂度与选择排序是一样的 但是效率有所提升
冒泡排序:
冒泡排序也和选择排序一样,属于非常简单易懂的排序算法。其算法思路就是从第一位数开始,与第二位数比大小,哪个数大放在第二位,换完后的第二位数与第三位数比,哪个大哪个放第三位,依次类推,循环一次后,最大的数就放在了最后面,如同泡泡一样从下面冒出来。
代码如下:
void bubble_sort(int arr[],int len)
{for (int i = 0; i < len-1; i++) //只需要循环len-1次 每循环一次 最值都会放入到最后面{int flag = 0; //插旗子 来判断循环是否发生交换for (int j = 0; j < len-i-1; j++) //两两比较大小 区间是[0,len-i-1] 由于下面用的是j+1 所以j<len-i-1 {if (arr[j] > arr[j+1]){swap(arr[j],arr[j+1]); //如果arr[j]>arr[j+1] 则交换flag = 1; //旗子置1}}if(flag == 0) break; //如果旗子没动 说明没有发生交换 也就是数组已经有序了 无需进行后续循环 }
}
时间复杂度为O(n^2)
计数排序:
如果给你一批数据,你又知道这批数据的区间,那么哪种排序算法所消耗的时间复杂度最小呢?答案就是计数排序。计数排序的原理类似于打点。例如,给你一组50个[0,100]的数据,计数排序会先创建一个大小为101的空数组p,这50个数分别对应p数组的下标,出现一次,则该p数组中下标为此数的值+1,比如50个数中有3个7,那么辅助数组p[7]的值++,p[7]最后值为3。最后再把这些值一次性打印出来。
void countSort(int arr[],int len)
{int max =arr[0]; //一般来说最大值都是已知的 直接调用就行 我比较懒 就干脆让排序自己找最大值了 for (int i = 1; i < len; i++) //数据量小还是可以的哈 数据量如果太大不推荐{if (arr[i] > max){max = arr[i];}}max++; //让max+1 放最大值 毕竟数组是从[0,max-1] int* p = calloc(max,sizeof(int));for (int j = 0; j < len; j++){p[arr[j]]++; //把arr[j]放入自己对于下标的p数组中}int j =0; //j置0 也可以重新创一个变量 用来放回arrfor (int i = 0; i < max; i++){while(p[i]>0) //如果该下标的值不为0 {arr[j++] = i; //把下标放进arr中p[i]--; }}
}
计数排序的时间复杂度为O(n)
更多推荐
排序算法01——冒泡排序、选择排序、鸡尾酒排序、计数排序
发布评论