原创
快速排序：（以下引用来自百度百科：）
基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，
然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key
我要评论 1 import java.util.*;
2
3 public class 二分搜索_快速排序 {
4
5 static int arr[];
6
7 static int BinarySearch(int left,int right,int x){ //二分查找
8 int mid=0;
9 while(true) {
10 mid=(left+right)/2;
11 if(x==arr[mid]) {
12 return mid;
13 }
14 else if(x<arr[mid]) {
15 right=mid-1;
16 }
17 else {
18 left=mid+1;
19 }
20 if(left<right) { //已经找不到
21 break;
22 }
23 }
24 return -1;
25 }
26
27 static int YiKuan(int left,int right) { //一趟快速排序
28 int x=0;
29 x=arr[left]; //存储基准记录
30 while(left<right) {
31 while(left<right && arr[right]>x) {
32 right--;
33 }
34 if(left<right) { //判断跳出条件是否合理
35 arr[left]=arr[right];
36 left++;
37 }
38 while(left<right && arr[left]<x) {
39 left++;
40 }
41 if(left<right) {
42 arr[right]=arr[left];
43 right--;
44 }
45 }
46 arr[left]=x;
47 return left;
48 }
49
50 static void Quan(int left,int right) { //快速排序
51 if(left<right) {
52 int mid=0;
53 mid=YiKuan(left,right);
54 Quan(left,mid-1);
55 Quan(mid+1,right);
56 }
57 }
58
59 public static void main(String args[]) {
60
61 Scanner reader=new Scanner(System.in);
62 System.out.print("输入数组大小： ");
63 int n=0;
64 n=reader.nextInt();
65 System.out.print("输入数组元素： ");
66 arr=new int[n];
67 for(int i=0;i<=n-1;i++) {
68 arr[i]=reader.nextInt();
69 }
70 Quan(0,n-1);
71 System.out.println("快速排序之后： ");
72 for(int i=0;i<=n-1;i++) {
73 System.out.print(arr[i]+" ");
74 }
75 System.out.print("\n");
76 System.out.print("请输入您要查找的值： ");
77 int x=0;
78 x=reader.nextInt();
79 int value=BinarySearch(0,n-1,x);
80 if(value!=-1) {
81 System.out.print("其索引为： "+value);
82 }
83 else {
84 System.out.println("the value not exist");
85 }
86 }
87 }
09:26:38
2018-06-18
如对本文有疑问， 点击进行留言回复！！
网友评论