本文主要是介绍七大排序算法之快排、冒泡，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
冒泡排序
思想：循环n次，交换左右两侧数据，外层每循环一次可以把无序中最大的（最小）的元素放到无序的最后面
时间复杂度：
平均：O(N^2)（一共循环：f(n) = (n-1)+(n-2)+...+2+1 = n*(n-1)/2 次）
O(f(n)) = n^2（只留f(n)的最高项，并且去掉最高项的系数）
最好：O(N)（优化冒泡排序：排序数列本身就有序的情况）
最坏：O(N^2)
空间复杂度：O(1)
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度
稳定性：稳定排序
八种排序的稳定性
不稳定：快速排序，选择排序，堆排序，希尔排序（快选堆希）
稳定：插入排序，冒泡排序，归并排序，基数排序（插冒归基）
算法的稳定性判断：排序前，2个相等的数在序列中的前后位置顺序，与，排序后，它们两个的前后位置顺序相同
代码实现：
// 左右两侧比较
public static void bubbleSort(int[] array) {for (int i = 0; i < array.length - 1; ++i) {for (int j = 0; j < array.length - i - 1; ++j) {if (array[j] > array[j + 1]) {int tmp = array[j];array[j] = array[j + 1];array[j + 1] = tmp;}}}
}// 优化
public static void bubbleSort2(int[] array) {for (int i = 0; i < array.length - 1; ++i) {boolean flag = true;for (int j = 0; j < array.length - i - 1; ++j) {if (array[j] > array[j + 1]) {flag = false;int tmp = array[j];array[j] = array[j + 1];array[j + 1] = tmp;}}if (flag) {break;// 排序序列本身已有序}}
}快速排序
思想：
1、找一个基准值（关键数）
方法1：排序序列中最左/右的数（一般用此方法）
方法2：随机取值
方法3：三数取中法
2、让整个数组中比基准值小的值放于基准值左侧，反之放于基准值右侧
方法1：左右下标法
方法2：挖坑法
方法3：前后下标法
3、将数组分成3部分：左、基准值、右
4、分而治之（子问题的思想）
时间复杂度：
平均：O(NlgN)
根据代码我们知道，每一层的递归操作次数为该次递归所传入的元素个数，忽略每次减去的枢轴（1个元素并没有给到下一层，但是每层这里减掉一个常数对复杂度的分析影响不大，所以暂时忽略），即：
第1层是n次，
第2层有2次递归，每次n/2次，共n次操作，
第3层有4次递归，每次n/4次，共n次操作，
……
（最后一层）第k层有k次递归，每次n/2^k次，共n次操作
由于递归结束的条件是只有一个元素，所以这里的n/2^k=1 => k=logn
即递归树的深度为logn
时间复杂度=每层的操作次数*树的深度=nlogn 即：O(nlgn);
最好：O(NlgN)
最坏：O(N^2)//排序序列是逆序的
空间复杂度：O(NlgN)；最坏时，O(N)
递归调用，为它的下一个递归调用函数开辟出一块新的空间，而每次的新的空间只需要一个temp存放基准元素即可。一共发生(logn(较好和一般情况下))，所以需要的空间是O(logn)，最坏的空间复杂度是（o(n)此时发生了n次调用）
稳定性：不稳定排序
代码实现：
1）左右下标法
public static void quickSort(int[] array, int beg, int end) {if(beg >= end) {return;}//partSort()完成基准值的选择以及数字交换一次的过程int index = partSort(array, beg, end);quickSort(array, beg, index - 1);quickSort(array, index + 1, end);}//左右下标
private static int partSort(int[] array, int beg, int end) {int left = beg;int right = end;int key = array[end];//基准值while(left < right) {while(left < right && array[left] <= key) {++left;//保证循环完毕之后left指向一个大于key的值}while(left < right && array[right] >= key) {--right;//保证循环完毕之后right指向一个小于key的值}if(left < right) {swap(array, left, right);//交换：此时left与right未相遇}}swap(array, left, end);//交换：此时left与right已相遇return left;
}private static void swap(int[] array, int num1, int num2) {int tmp = array[num1];array[num1] = array[num2];array[num2] = tmp;
}2）挖坑法：空出一个位置最后存放基准值
private static int partSort1(int[] array, int left, int right) {int key = array[right];// 基准值while (left < right) {while (left < right && array[left] <= key) {++left;// 保证循环完毕之后left指向一个大于key的值}array[right] = array[left];//坑位while (left < right && array[right] >= key) {--right;// 保证循环完毕之后right指向一个小于key的值}array[left] = array[right];//坑位}//left先走，所以最后一个坑位在right下标array[right] = key;//找出key基准值适合的位置return right;
}3）前后下标法
private static int partSort2(int[] array, int left, int right) {if(left < right) {int key = array[right];// 基准值int cur = left;int pre = cur - 1;while (cur < right) {//当cur小于key时，pre就一直跟在cur之后，所以第二个条件不会成立while (array[cur] < key && ++pre != cur) {swap(array, cur, pre);//当cur大于key值时，就不会执行++pre，就会拉开pre的距离//所以在pre和cur之间的值都是大于pre的值//而进入该循环时，条件成立，将小于key的值与pre~cur之间的值交换}++cur;}swap(array, ++pre, right);return pre;}return -1;
}
这篇关于七大排序算法之快排、冒泡的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
