Java简单的冒泡排序+二分法查找实践
给出数组
num={14,23231,53534,123,321,23,4,5,76,8,5,2,3,3245,34434324,123123,53563,232,1233,44421,1},
要求找出数组是否含有123,如果含有,找出123在原数组的位置
public class Main {
public static void main(String[] args) {
int[] num = {14,23231,53534,123,321,23,4,5,76,8,5,2,3,3245,34434324,123123,53563,232,1233,44421,1};
int target = 123;
int[] oldNum = num.clone();
bubbleSort(num);
int position = binarySearch(num, target);
if (position != -1){
int count=0;
for (int i=0; i<oldNum.length;i++){
if (oldNum[i] == target){
count = i;
}
}
System.out.println("Found " + num[position] + " at " + count);
}else{
System.out.println("Sorry, not found.");
}
}
public static void bubbleSort(int[] num){
for (int pass=0; pass<num.length-1;pass++){
for (int i=0; i<num.length-1-pass; i++){
int tmp;
if (num[i] > num[i+1]){
tmp = num[i];
num[i] = num[i+1];
num[i+1] = tmp;
}
}
}
}
public static int binarySearch(int[] num, int target){
int left = 0;
int right = num.length-1;
while (left <= right){
int mid = (left+right)/2;
if (num[mid] == target){
return mid;
}
if (num[mid] < target){
left = mid + 1;
}else{
right = mid - 1;
}
}
return -1;
}
}
public static void main(String[] args) {
int[] num = {14,23231,53534,123,321,23,4,5,76,8,5,2,3,3245,34434324,123123,53563,232,1233,44421,1};
int target = 123;
int[] oldNum = num.clone();
bubbleSort(num);
int position = binarySearch(num, target);
if (position != -1){
int count=0;
for (int i=0; i<oldNum.length;i++){
if (oldNum[i] == target){
count = i;
}
}
System.out.println("Found " + num[position] + " at " + count);
}else{
System.out.println("Sorry, not found.");
}
}
public static void bubbleSort(int[] num){
for (int pass=0; pass<num.length-1;pass++){
for (int i=0; i<num.length-1-pass; i++){
int tmp;
if (num[i] > num[i+1]){
tmp = num[i];
num[i] = num[i+1];
num[i+1] = tmp;
}
}
}
}
public static int binarySearch(int[] num, int target){
int left = 0;
int right = num.length-1;
while (left <= right){
int mid = (left+right)/2;
if (num[mid] == target){
return mid;
}
if (num[mid] < target){
left = mid + 1;
}else{
right = mid - 1;
}
}
return -1;
}
}
代码局限性:因为二分法查找只能根据有序排列的数组进行查找,所以当确认数字存在于数组之后,去查找数字的在原数组位置时是一个普通的线形for loop。
要点:二分法只能查询排序过的数组;array的类型是reference,如果更改array以后还需要原来的array就需要提前clone;