首页 > 代码库 > java排序(整理)
java排序(整理)
冒泡排序（面试都要问的算法）
一、基本思想：每次比较相邻的两个 元素，按需调整顺序
二、题目：要求将 12 35 99 18 76 这 5 个数进行从大到小排序
三、思路：
（1）先比较第 1 位和第 2 位的大小，12<35，因为希望越小越靠后，所以要调整两者顺序，交换后的结果：35 12 99 18 76
（2）现在比较第 2 位和第 3 位的大小，12<99，所以需要交换位置，交换后的结果为：35 99 12 18 76
（3）接着比较第 3 位和第 4 位的大小，12<18，交换后的结果为：35 99 18 12 76
（4）最后比较第 4 位和第 5 位的大小，12<76，交换后的结果为：35 99 18 76 12
（5）经过 4 次后我们发现 5 个数中最小的一个数已经就位，每将一个数归位我们称其为“一趟”；
（6）现在我们开始第二趟，目标将第 2 小的数归位，根据之前逻辑，还是从第 1 个数和第 2 个数开始比较上：
35 99 18 76 12 --①--> 99 35 18 76 12 --②--> 99 35 18 76 12 --③--> 99 35 76 18 12
在第一趟比较就知道第 5 位是最小的，所以第 4 位不用和第 5 位比较，这一趟只需比较 3 次
（7）第3趟：99 35 76 18 12 --> 99 35 76 18 12 --> 99 76 35 18 12 （比较 2 次）
（8）第4趟：99 76 35 18 12 --> 99 76 35 18 12 ,有4个数已经就位，那么最后一个数无须比较，它就是最大的
【总结】如果有 n 个数进行排序，只需将 n-1 个数归位，即要进行 n-1 趟操作，而每一趟开始都从第 1 位进行相邻的两个数 进行比较，将小的那个数放在后面，已经归位的就不用进行比较。
【特点】冒泡算法的核心部分是双重嵌套循环，可以看出时间复杂度是 O(N2)，这是一个非常高的时间复杂度。
这里使用Java给出简单的算法过程。
/** * 冒泡排序，从小到大 * @param args */ public static void main(String args[]){ int nums[] = new int[] { 12, 35, 99, 18, 76,2,4,5,6,77,8,9 }; for(int i=0;i<nums.length-1;i++){ //int j=0;j<nums.length-1;j++ //int j=0;j<nums.length-1-i;j++ //第二种，优与第一种 for(int j=0;j<nums.length-1-i;j++){ int f=nums[j];//第一个数 int s=nums[j+1];//第二个数 if(s<f){ int temp=f; nums[j]=nums[j+1]; nums[j+1]=temp; } } } output(nums); } public static void output(int num[]){ for(int n:num){ System.out.print(n +" "); } }
快速排序（见证亚当和夏娃的爱情之旅）
一、场景：对 6 1 2 7 9 3 4 5 10 8 这 10 个数进行排序
二、思路：
先找一个基准数（一个用来参照的数），为了方便，我们选最左边的 6，希望将 >6 的放到 6 的右边，<6 的放到 6 左边。如：3 1 2 5 4 6 9 7 10 8
先假设需要将 6 挪到的位置为 k，k 左边的数 <6，右边的数 >6
（1）我们先从初始数列“6 1 2 7 9 3 4 5 10 8 ”的两端开始“探测 ”，先从右边往左找一个 <6 的数，再从左往右找一个 >6 的数，然后交换。我们用变量 i 和变量 j 指向序列的最左边和最右边。刚开始时最左边 i=0 指向 6，最右边 j=9 指向 8
（2）现在设置的基准数是最左边的数，所以序列先右往左移动（j--），当找到一个 <6 的数（5）就停下来。接着序列从左往右移动（i++），直到找到一个 >6 的数又停下来（7）；
（3）两者交换，结果：6 1 2 5 9 3 4 7 10 8；
（4）j 的位置继续向左移动（友情提示：每次都必须先从 j 的位置出发），发现 4 满足要求，接着 i++ 发现 9 满足要求，交换后的结果：6 1 2 5 4 3 9 7 10 8；
（5）目前 j 指向的值为 9，i 指向的值为 4，j-- 发现 3 符合要求，接着 i++ 发现 i=j，说明这一轮移动结束啦。现在将基准数 6 和 3 进行交换，结果：3 1 2 5 4 6 9 7 10 8；现在 6 左边的数都是 <6 的，而右边的数都是 >6 的，但游戏还没结束
（6）我们将 6 左边的数拿出来先：3 1 2 5 4，这次以 3 为基准数进行调整，使得 3 左边的数 <3，右边的数 >3，根据之前的模拟，这次的结果：2 1 3 5 4
（7）再将 2 1 抠出来重新整理，得到的结果： 1 2
（8）剩下右边的序列：9 7 10 8 也是这样来搞，最终的结果： 1 2 3 4 5 6 7 8 9 10 （具体看下图）
快速排序的每一轮处理其实就是将这一轮的基准数归位，当所有的基准数归位，排序就结束啦
java代码实现：
/** * 查找出中轴（默认是最低位low）的在numbers数组排序后所在位置 * * @param numbers * 带查找数组 * @param low * 开始位置 * @param high * 结束位置 * @return 中轴所在位置 */ public static int getMiddle(int[] numbers, int low, int high) { int temp = numbers[low]; // 数组的第一个作为中轴 while (low < high) { while (low < high && numbers[high] > temp) { high--; } numbers[low] = numbers[high];// 比中轴小的记录移到低端 while (low < high && numbers[low] < temp) { low++; } numbers[high] = numbers[low]; // 比中轴大的记录移到高端 } numbers[low] = temp; // 中轴记录到尾 return low; // 返回中轴的位置 } /** * * @param numbers * 带排序数组 * @param low * 开始位置 * @param high * 结束位置 */ public static void quickSort(int[] numbers, int low, int high) { if (low < high){ int middle = getMiddle(numbers, low, high); // 将numbers数组进行一分为二 quickSort(numbers, low, middle - 1); // 对低字段表进行递归排序 quickSort(numbers, middle + 1, high); // 对高字段表进行递归排序 } } /** * 快速排序 * * @param numbers * 带排序数组 */ public static void quick(int[] numbers) { // 查看数组是否为空 if (numbers.length > 0) { quickSort(numbers, 0, numbers.length - 1); } } /** * 打印 * @param numbers */ public static void printArr(int[] numbers) { for (int i = 0; i < numbers.length; i++) { System.out.print(numbers[i] + ","); } System.out.println(""); } public static void main(String[] args) { int[] numbers = { 10, 20, 15, 0, 6, 7, 2, 1, -5, 55 }; System.out.print("排序前："); printArr(numbers); quick(numbers); System.out.print("快速排序后："); printArr(numbers); }
参考文章：
http://www.cnblogs.com/liqingwen/p/4994261.html
http://www.cnblogs.com/0201zcr/p/4763806.html
java排序(整理)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。