快速排序_二分搜索
程序员文章站
2022-12-20 21:52:53
原创 快速排序:(以下引用来自百度百科:https://baike.baidu.com/item/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/369842?fromtitle=%E5%BF%AB%E9%80%9F%E6%8E%92%E ......
原创
快速排序:(以下引用来自百度百科:)
基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,
然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用数组的第一个数)作为关键数据,然后将所有
比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。值得注意的是,快速排序不
是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。
一趟快速排序的算法是:
1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;
2)以第一个数组元素作为关键数据,赋值给key,即key=A[0];
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
的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。
另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。
二分查找:(以下引用来自百度百科:)
首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录
将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过
程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
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
上一篇: Java学习笔记三十一:Java 包(package)
下一篇: Java爬虫爬取京东商品信息