选择排序
选择排序是从数组下标0（下标为0的元素）开始依次固定与之后的所有元素进行比较，比被固定的元素小则与之交换，否则不交换，一轮下来可以确定出被固定下标的元素是排在第一位的元素即最小的元素
冒泡排序
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
二分法查找
二分法查找是建立在已经排好序的前提下，确定该区间的中间位置K（2）将查找的值T与array[k]比较。若相等，查找成功返回此位置；否则确定新的查找区域，继续二分查找。区域确定如下：a.array[k]>T 由数组的有序性可知array[k,k+1,……,high]>T;故新的区间为array[low,……，K-1]b.array[k]<T 类似上面查找区间为array[k+1,……，high]。每一次查找与中间值比较，可以确定是否查找成功，不成功当前查找区间缩小一半，递归找，即可。时间复杂度:O(log2n)
public class Sort {
public static void main(String args[]) {
int[] arr = { 4, 56, 23, 166, 2 };
// selectSort(arr); //选择排序
// bubbly(arr); //冒泡排序
Arrays.sort(arr); // JDK自身的排序
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
// 二分法查找
int key = 56;
int index = halfSearch(arr, key);
System.out.println(index);
}
// 选择排序
public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] > arr[j]) {
exchange(arr, i, j);
}
}
}
}
// 冒泡排序
public static void bubbly(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
exchange(arr, j, j + 1);
}
}
}
}
// 交换
public static void exchange(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 二分法查找（数组必须是已经排好序的）
public static int halfSearch(int[] arr, int key) {
int min = 0, max = arr.length - 1, mid;
while (min <= max) {
mid = (min + max) / 2;
if (key > arr[mid])
min = mid + 1;
else if (key < arr[mid])
max = mid - 1;
else
return mid;
}
return -1;
}
}
网友评论