2. 交换排序
2.1 冒泡排序
原理: 比较两个相邻的元素, 将值大的元素交换至右端
思路: 依次比较相邻的两个数, 将小数放在前面, 大数放在后面即在第一趟: 首先比较第 1 个和第 2 个数, 将小数放前, 大数放后然后比较第 2 个数和第 3 个数, 将小数放前, 大数放后, 如此继续, 直至比较最后两个数, 将小数放前, 大数放后重复第一趟步骤, 直至全部排序完成
举例说明: 要排序数组: int[] arr={6,3,8,2,9,1};
第一趟排序:
第一次排序: 6 和 3 比较, 6 大于 3, 交换位置: 3 6 8 2 9 1
第二次排序: 6 和 8 比较, 6 小于 8, 不交换位置: 3 6 8 2 9 1
第三次排序: 8 和 2 比较, 8 大于 2, 交换位置: 3 6 2 8 9 1
第四次排序: 8 和 9 比较, 8 小于 9, 不交换位置: 3 6 2 8 9 1
第五次排序: 9 和 1 比较: 9 大于 1, 交换位置: 3 6 2 8 1 9
第一趟总共进行了 5 次比较, 排序结果: 3 6 2 8 1 9
---------------------------------------------------------------------
第二趟排序:
第一次排序: 3 和 6 比较, 3 小于 6, 不交换位置: 3 6 2 8 1 9
第二次排序: 6 和 2 比较, 6 大于 2, 交换位置: 3 2 6 8 1 9
第三次排序: 6 和 8 比较, 6 大于 8, 不交换位置: 3 2 6 8 1 9
第四次排序: 8 和 1 比较, 8 大于 1, 交换位置: 3 2 6 1 8 9
第二趟总共进行了 4 次比较, 排序结果: 3 2 6 1 8 9
---------------------------------------------------------------------
第三趟排序:
第一次排序: 3 和 2 比较, 3 大于 2, 交换位置: 2 3 6 1 8 9
第二次排序: 3 和 6 比较, 3 小于 6, 不交换位置: 2 3 6 1 8 9
第三次排序: 6 和 1 比较, 6 大于 1, 交换位置: 2 3 1 6 8 9
第二趟总共进行了 3 次比较, 排序结果: 2 3 1 6 8 9
---------------------------------------------------------------------
第四趟排序:
第一次排序: 2 和 3 比较, 2 小于 3, 不交换位置: 2 3 1 6 8 9
第二次排序: 3 和 1 比较, 3 大于 1, 交换位置: 2 1 3 6 8 9
第二趟总共进行了 2 次比较, 排序结果: 2 1 3 6 8 9
---------------------------------------------------------------------
第五趟排序:
第一次排序: 2 和 1 比较, 2 大于 1, 交换位置: 1 2 3 6 8 9
第二趟总共进行了 1 次比较, 排序结果: 1 2 3 6 8 9
---------------------------------------------------------------------
最终结果: 1 2 3 6 8 9
---------------------------------------------------------------------
由此可见: N 个数字要排序完成, 总共进行 N-1 趟排序, 每 i 趟的排序次数为 (N-i) 次, 所以可以用双重循环语句, 外层控制循环多少趟, 内层控制每一趟的循环次数, 即
- public static void BubbleSort(int[] arr) {
- int temp;// 定义一个临时变量
- for(int i=0;i<arr.length-1;i++){// 冒泡趟数
- for(int j=0;j<arr.length-i-1;j++){
- if(arr[j+1]<arr[j]){
- temp = arr[j];
- arr[j] = arr[j+1];
- arr[j+1] = temp;
- }
- }
- }
- }
2.2 快速排序
单单看以上解释还是有些模糊, 可以通过实例来理解它, 下面通过一组数据来进行排序过程的解析:
原数组:{3,7,2,9,1,4,6,8,10,5}
期望结果:{1,2,3,4,5,6,7,8,9,10}
花了点时间撸了下面这张快速排序示意图:
Demo 步骤解析:
1. 一开始选定数组的最后一个元素 5 作为基准值, 也就是最终排序结果应该是以 5 为界限划分为左右两边
2. 从左边开始, 寻找比 5 大的值, 然后与 5 进行调换(因为如果比 5 小的值本来就应该排在 5 前面, 比 5 大的值调换之后就去到了 5 的后面), 一路过来找到了 7, 将 7 与 5 调换, 结束此次遍历
3. 从右边开始, 由于 7 已经是上一轮排好序的便不再动它, 从 10 开始, 一路向左遍历, 寻找比 5 小的值, 然后与 5 进行调换(因为如果比 5 大的值本来就应该排在 5 后面, 比 5 小的值调换之后就去到了 5 的后前面), 一路过来找到了 4, 将 4 与 5 调换, 结束此次遍历
4. 从左边开始, 由于 3 和 4 都是前两轮已经排好序的便不再动它, 从 2 开始, 一路向右遍历, 寻找比 5 大的值, 然后与 5 进行调换(道理同步骤 2), 一路过来找到了 9, 将 9 与 5 调换, 结束此次遍历
5. 从右边开始, 由于排在 9 后面的那几个数字都是上几轮排好序的便不再动它, 从 1 开始, 一路向右遍历, 寻找比 5 小的值, 然后与 5 进行调换(道理同步骤 3), 一下子就找到了 1, 将 1 与 5 调换, 结束此次遍历
6. 这个时候, 发现 5 的左右两边都是排好序了的, 所以结束此轮排序, 5 的左右两边抽出来各自进行下一轮的排序, 规则同上, 直到无法再拆分下去, 即完成了整体的快速排序
Java 代码
- /**
- * 快速排序
- * @author IT_ZJYANG
- */
- public class QuickSort {
- /**
- * 将数组的某一段元素进行划分, 小的在左边, 大的在右边
- * @param a
- * @param start
- * @param end
- * @return
- */
- public
- static int divide(int[] a, int start, int end){
- // 每次都以最右边的元素作为基准值
- int base = a[end];
- //start 一旦等于 end, 就说明左右两个指针合并到了同一位置, 可以结束此轮循环
- while(start < end){
- while(start < end && a[start] <= base)
- // 从左边开始遍历, 如果比基准值小, 就继续向右走
- start++;
- // 上面的 while 循环结束时, 就说明当前的 a[start]的值比基准值大, 应与基准值进行交换
- if(start < end){
- // 交换
- int temp = a[start];
- a[start] = a[end];
- a[end] = temp;
- // 交换后, 此时的那个被调换的值也同时调到了正确的位置(基准值右边), 因此右边也要同时向前移动一位
- end--;
- }
- while(start < end && a[end] >= base)
- // 从右边开始遍历, 如果比基准值大, 就继续向左走
- end--;
- // 上面的 while 循环结束时, 就说明当前的 a[end]的值比基准值小, 应与基准值进行交换
- if(start < end){
- // 交换
- int temp = a[start];
- a[start] = a[end];
- a[end] = temp;
- // 交换后, 此时的那个被调换的值也同时调到了正确的位置(基准值左边), 因此左边也要同时向后移动一位
- start++;
- }
- }
- // 这里返回 start 或者 end 皆可, 此时的 start 和 end 都为基准值所在的位置
- return end;
- }
- /**
- * 排序
- * @param a
- * @param start
- * @param end
- */
- public
- static void sort(int[] a, int start, int end){
- if(start > end){
- // 如果只有一个元素, 就不用再排下去了
- return;
- }
- else{
- // 如果不止一个元素, 继续划分两边递归排序下去
- int partition = divide(a, start, end);
- sort(a, start, partition-1);
- sort(a, partition+1, end);
- }
- }
- }
来源: http://www.bubuko.com/infodetail-2514451.html