赞
踩
1. 快速排序原理
2. 快排的递归实现
3. 代码
4. 测试排序的速度
1,排序原理
快速排序(Quicksort)是对冒泡排序的一种改进。
基本思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列
2,快速排序的示意图
3,快速排序的应用实例
需求:对{20,7,10,-12,-3,9}进行快速排序
代码实现:
package com.atxiaopeng.sort; import java.util.Arrays; public class QuickSort { public static void main(String[] args) { // TODO Auto-generated method stub int []arr = {20,7,10,-12,-3,9}; quickSort(arr, 0,arr.length-1); System.out.println(Arrays.toString(arr)); } public static void quickSort(int[]a,int left,int right) { int l = left; int r = right; int pivot = a[(left+right)/2]; int temp = 0; while (l<r) { while (a[l]<pivot) { l+=1; } while (a[r]>pivot) { r-=1; } if (l>=r) { break; } temp = a[l]; a[l] = a[r]; a[r] = temp; if (a[l] == pivot) { r-=1; } if (a[r] == pivot) { l+=1; } } if (l == r) { r-=1; l+=1; } //向左递归 if (left < r) { quickSort(a, left, r); } if (right>l) { quickSort(a, l, right); } } }
排序的结果
Date date1= new Date();
SimpleDateFormat s1 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String f1 = s1.format(date1);
System.out.println("排序前的时间:"+f1);
int []arr1 = new int[800000];
for (int i = 0; i < arr1.length; i++) {
arr1[i] = (new Random().nextInt()+1)*800000;
}
quickSort(arr1, 0, arr1.length-1);
Date date2= new Date();
SimpleDateFormat f2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String f3 = f2.format(date2);
速度还是比较稳定的,平均在1秒左右
1. 归并排序的原理
2. 分析
3. 案例及代码实现
4. 测试排序速度
1,归并排序的原理
归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)
2,分析
归并的过程:
借助一个辅助的数组temp进行存储。
然后再把排好序的数组赋值个原数组。
思路:
3,案例及代码
需求:排序 {8,4,5,7,1,3,6,2};
代码实现:
package com.atxiaopeng.sort; import java.util.Arrays; public class MergetSort { public static void main(String[] args) { // TODO Auto-generated method stub int[] arr = {8,4,5,7,1,3,6,2}; int[] temp = new int [arr.length]; mergetSort(arr, 0, arr.length-1, temp); System.out.println("最终结果:"+Arrays.toString(arr)); } //分+合的方法 public static void mergetSort(int[]arr,int left,int right,int[]temp) { if (left<right) { int mid = (left+right)/2; //向左进行递归 mergetSort(arr, left, mid, temp); //向右进行递归 mergetSort(arr, mid+1, right, temp); merget(arr, left, mid, right, temp); } } //合的方法 public static void merget(int arr[],int left,int mid,int right,int[]temp) { int i = left; int j = mid+1; int t = 0; while (i<=mid&&j<=right) { if (arr[i]<=arr[j]) { temp[t] = arr[i]; t++; i++; }else { temp[t] = arr[j]; t++; j++; } } while (i<=mid) { temp[t] = arr[i]; t++; i++; } while (j<=right) { temp[t] = arr[j]; t++; j++; } //把temp拷贝导arr[]数组中 t = 0; int templeft = left; System.out.println("辅助数组:left"+left+" right"+right+Arrays.toString(temp)); while (templeft<=right) { arr[templeft] = temp[t]; t++; templeft++; } System.out.println("原始数组:left"+left+" right"+right+Arrays.toString(arr)); System.out.println("=========================================="); } }
排序的过程及结果:
4,测试排序速度
需求:排序80000个随机数
代码实现:
int arr1 [] = new int [80000]; int temp1[] = new int [arr1.length]; for (int i = 0; i < temp1.length; i++) { arr1[i] = (new Random().nextInt()+1)*80000; } Date date = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String f1 = simpleDateFormat.format(date); System.out.println("归并排序前:"+f1); mergetSort(arr1, 0, arr1.length-1, temp1); Date date2 = new Date(); SimpleDateFormat f2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String f3 = f2.format(date2); System.out.println("归并排序后:"+f3);
排序时间:
平均时间不到1秒。
欢迎指正,共同进步。
赞
踩
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。