算法之排序 |
您所在的位置：网站首页 › 城市最低气温排第三是按从高到低排吗 › 算法之排序 |
算法之排序
|
文章目录
排序算法的分类复杂度为O(n^2 )的排序算法冒泡排序插入排序选择排序
复杂度为O(nlogn)的排序算法归并排序快速排序
复杂度为O(n)的排序算法计数排序桶排序
各种排序算法的对比
在生活中，我们离不开排序。例如上体育课时，同学们会按照身高顺序进行排队；又如每一场考试后，老师会按照考试成绩排名次。在编程的世界中，应用到排序的场景也比比皆是。例如当开发一个学生管理系统时，需要按照学号从小到大进行排序；当开发一个电商平台时，需要把同类商品按价格从低到高进行排序。 排序算法的分类根据时间复杂度可以将排序算法分为三类 排序算法时间复杂度第一类冒泡、插入、选择O(n^2)第二类快排、归并O(nlogn)第三类桶、计数、基数O(n)根据排序算法的稳定性还可以将排序算法的分为两类 如果值相同的元素在排序后仍然保持着排序前的顺序，则这样的排序算法是稳定排序；如果值相同的元素在排序后打乱了排序前的顺序，则这样的排序算法是不稳定排序。 第一类：时间复杂度为O(n^2 )的排序算法，因为时间复杂度比较高所以适合小规模数据的排序。 冒泡排序冒泡排序之所以叫冒泡排序，正是因为这种排序算法的每一个元素都可以像小气泡 一样，根据自身大小，一点一点地向着数组的一侧移动。 冒泡排序是一种稳定排序，值相等的元素并不会打乱原本的顺序。由于该排序算法 的每一轮都要遍历所有元素，总共遍历（元素数量-1）轮，所以平均时间复杂度 是O(n^2 )。 冒泡排序的代码实现 public static void bubbleSort(int[] array) { for (int i = 0; i endIndex) { return; } // 得到基准元素位置 int pivoIndex = partition(arr, startIndex, endIndex); // 根据基准元素，分为两部分进行递归排序 quickSort(arr, startIndex, pivoIndex - 1); quickSort(arr, pivoIndex + 1, endIndex); } /** * 分治(双边循环法) * @param arr 待交换数组 * @param startIndex 起始下标 * @param endIndex 结束下标 */ private static int partition(int[] arr, int startIndex, int endIndex) { // 取第1个位置（也可以选择随机位置）的元素作为基准元素 int pivot = arr[startIndex]; int left = startIndex; int right = endIndex; while(left != right) { // 控制right指针比较并左移 while(leftpivot) { right--; } // 控制left指针比较并右移 while(left |
【本文地址】
今日新闻 |
推荐新闻 |