折半查找_快速排序

majiasheng 2018-09-25 原文

折半查找_快速排序

折半查找链接：https://www.baidu.com/link?url=yNyTQeYRL5xwA0aA9W8iAUVeroe87jU8j1v5qTrvYJ8uPCU8O-Pgw9oHg-TzHZwc3Hh3Lly8fkEw4fGaiUjKXa-n4rTu9eVQY0mdn-s_ttwHYINPLm7irBP5ivR4JrDrJUVm3KvFkgrlf8D-id7e2ebRpTZmJdaPfOeytTEVd8yWZUtGOwnNOtPnzxIwuQmnw68xdJ6dnH-pi2c7CEEiIq&wd=&eqid=e9e6d3a700016a7b000000065baa4f2b

快速排序链接：https://www.baidu.com/link?url=aBlnbNlAyrTNyWuH3GPZxBL06azwcR6zaw6WfinkweUldAXLYHrSUP4WqbhrmkO3sAM1BdIiIQ3rxyHlkmtafrOgi7yXnqvz0VJaGRp8r17NmC_0l-NrzYdGsA7o9xQ0pVma_KakZOyqxVn8i5GaU03xodWH3yyICcjEQ9z0csj_jdLZQpveRFZljyXmMf5hfZjdpqkeHS1kNl0ngATXAI9da95juDoUl1fdN6sIFWa&wd=&eqid=d76fab2200014df1000000065baa4fbb

 1 package Mypackage;
 2                       
 3 import java.util.*;
 4 
 5 public class 折半查找_快速排序 {
 6     //快速排序
 7     static int a[]=new int[100];
 8     static int n=0;
 9     static int num=0;
10     
11     static void quicksort(int left,int right)
12     {
13         int temp=0;
14         int i=0;
15         int j=0;
16         int t=0;
17         if(left>right)
18             return;        
19         temp=a[left];
20         i=left;
21         j=right;
22         while(i!=j)
23         {  
24             while(i<j && a[j]>=temp)
25                 j--;
26             while(i<j && a[i]<=temp)
27                 i++;
28             //两个数的交换
29             if(i<j)
30             {
31                t=a[j];
32                a[j]=a[i];
33                a[i]=t;
34                 
35             }
36         }
37         //基准数归位
38         a[left]=a[i];
39         a[i]=temp;
40         
41         quicksort(left,i-1);
42         quicksort(i+1,right);
43         
44         return;
45     }
46     
47     //折半查找
48     static int BinarySearch(int start, int end,int num)
49     {
50         int mid=0;
51         while(start<=end)
52         {
53           mid=(start+end)/2;
54           if(num==a[mid]) {
55               return mid;//返回到下标
56           }
57           else if(num>a[mid])
58           {
59             start=mid+1;  
60           }
61           else {
62               end=mid-1;
63           }    
64         }
65         
66         return -1;
67     }
68     public static void main(String[] args) {
69         int start=1;
70         int end=0;
71         int i=0;
72         Scanner reader=new Scanner(System.in);
73         System.out.print("输入数组的长度为:");
74           n=reader.nextInt();  
75           end=n;
76           for(i=1;i<=n;i++)
77           {
78               a[i]=reader.nextInt();
79           }
80           
81            quicksort(1,n);
82         System.out.println("排序后的数组为:");
83          for(i=1;i<=n;i++)
84          {
85              System.out.print(+a[i]+" ");
86          }
87          System.out.println("\n");
88          System.out.println("请你输入你查找的值：");
89           num=reader.nextInt();
90           int value=BinarySearch(start,end,num);
91           if(value!=-1)
92               System.out.println("其索引值："+value);
93           else
94               System.out.println("the value not exist");  
95     }
96 }