java实现插入、冒泡、选择、快速排序、二分查找
jopen
10年前
一. 直接插入排序
void insertSort( int[] a){
for( int i=1;i if (a[i] temp = a[i]; //1
a[i] = a[i-1]; //2
// 继续和前面的进行比较
for( int j=i-2; j>=0; j--){
if(temp < a[j])
a[j+1] =a[j]; //3
}
a[j+1] = temp; //4
}
}
}
for( int i=1;i
a[i] = a[i-1]; //2
// 继续和前面的进行比较
for( int j=i-2; j>=0; j--){
if(temp < a[j])
a[j+1] =a[j]; //3
}
a[j+1] = temp; //4
}
}
}
算法(简要描述):
1. temp保存被比较的数值
2. 前一位数值移动到被比较的数值的位置
3. 前面的继续往后移动
4. 把被比较的数值放到适当的位置
二.冒泡排序
冒泡排序，就是从最底那个开始往上比较，遇到比它小的就交换，相当于过五关看六将，不断地向前冲。接着循环第二个...
+-----+ void bubbleSort( int[] a){
| a[6] | //每个都进行冒泡(一个一个来)
+-----+ for ( int i=0; i | a[5] |
+-----+ //和后面的每个都进行比较(过五关看六将)
| a[4] | for ( int j=i; j +-----+ if (a[j]>a[j+1]){
| a[3] | temp = a[j];
+-----+ a[j] = a[j+1];
| a[2] | a[j+1] = temp;
+-----+ }
| a[1] | }
+-----+ }
| a[0] | }
+-----+
| a[6] | //每个都进行冒泡(一个一个来)
+-----+ for ( int i=0; i
+-----+ //和后面的每个都进行比较(过五关看六将)
| a[4] | for ( int j=i; j
| a[3] | temp = a[j];
+-----+ a[j] = a[j+1];
| a[2] | a[j+1] = temp;
+-----+ }
| a[1] | }
+-----+ }
| a[0] | }
+-----+
三.选择排序
选择排序，就是选择最小的，然后置换，循环再找到最小的，再置换...
void selectSort( int[] a){
for ( int i=0; i small = i;
//找出最小的
for ( int j=i+1; j if (a[small]>a[j]){
small = j;
}
}
//置换位置
if (i != small){
temp = a[small];
a[small] = a[i];
a]i] = temp;
}
}
}
for ( int i=0; i
//找出最小的
for ( int j=i+1; j
small = j;
}
}
//置换位置
if (i != small){
temp = a[small];
a[small] = a[i];
a]i] = temp;
}
}
}
四.快速排序
快速排序的基本过程:
得到枢轴索引：compare首先从high位置向前搜索找到第一个小于compare值的索引，并置换(这时high索引位置上的值为compare 值)；然后从low位置往后搜索找到第一个大于compare值的索引，并与high索引上的值置换(这时low索引位置上的值为compare值)；重 复这两步直到low=high为止。
得到枢轴索引后，则递归进行枢轴两边的队列的排序....
void quickSort( int[] a, int low, int high) {
p = get(a, low, high);
quickSort(a, low, p-1);
quickSort(a, p+1, high);
}
int get( int[] a, int low, int high){
compare = a[low];
while(low < high){ //无论如何置换, 被置换的都包含compare的值
while(low=compare)
high--;
//在 low
temp = a[low];
a[low] = a[high];
a[high] = temp;
while(low low++;
//在 lowcompare并置换
temp = a[low];
a[low] = a[high];
a[high] = temp;
}
return low; //while(low==hight)停止循环, 并返回枢轴位置
}
p = get(a, low, high);
quickSort(a, low, p-1);
quickSort(a, p+1, high);
}
int get( int[] a, int low, int high){
compare = a[low];
while(low < high){ //无论如何置换, 被置换的都包含compare的值
while(low
high--;
//在 low
temp = a[low];
a[low] = a[high];
a[high] = temp;
while(low
//在 low
temp = a[low];
a[low] = a[high];
a[high] = temp;
}
return low; //while(low==hight)停止循环, 并返回枢轴位置
}
五.二分查找
二分查找原理很容易懂，想象为二叉查找树就明白了。
int binarySearch( int[] a, int value){
int low = 0;
int high = a.length-1;
while(low <= high){
mid = (low+high)/2; //**
if (a[mid] == value)
return mid;
else if (a[mid] > value)
high = mid-1;
else
low = mid +1;
}
return -1;
}
int low = 0;
int high = a.length-1;
while(low <= high){
mid = (low+high)/2; //**
if (a[mid] == value)
return mid;
else if (a[mid] > value)
high = mid-1;
else
low = mid +1;
}
return -1;
}
解决的方法是mid = low/2 + high/2。这样用2先除一下，就不会溢出了。