4.1 基础算法
4.1.1 冒泡排序
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]){int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}
}
4.1.2 二分查找
public static int binSearch(int[] array, int target){int low = 0, high = array.length, mid = 0;while(low <= high){mid = low + (high - low) / 2;if(array[mid] == target){return mid;}else if(target > array[mid]){low = mid + 1;}else{high = mid - 1;}}return -1;
}
4.1.3 插入排序
public static int[] insertSort(int[] arr){// 取出未排序的第一个元素for(int i = 1; i < arr.length; i++){int value = arr[i]; // 取出未排序的第一个元素int index = i - 1; // 已排序的最后一个位置while(index >= 0 && value < arr[index]){// 未排序的第一个元素小于已排序的元素（从后往前）arr[index + 1] = arr[index]; // 原来排序的元素移动到后边index--; // index指向已排序的元素，从后往前移动地插入}arr[index + 1] = value; // 将元素插入到刚好arr[x]的前边。}return arr;
}public static int[] insertSort(int[] arr){for(int i = 1; i < arr.length; i++){int value = arr[i];int index = i - 1;while(index >= 0 && value < arr[index]){arr[index + 1] = arr[index--];}arr[index + 1] = value;}return arr;
}
4.1.4 快速排序
public static void quickSort(int[] arr, int low, int high){if(low < high){int pivot = partition(arr,low,high);quickSort(arr,low,pivot - 1);quickSort(arr,pivot + 1, high);}
}private static int partition(int[] arr, int low, int high){int pivot = arr[high];while(low < high){while(low < high && arr[low] < pivot){low++;}arr[high] = arr[low];while(low < high && arr[high] >= pivot){high--;}arr[low] = arr[high];}arr[high] = pivot;return high;
}
4.1.5 归并排序
package study.sort;public class Merge {//归并排序所需要的辅助数组private static Comparable[] assist;//对数组内的元素进行排序public static void sort(Comparable[] a){assist = new Comparable[a.length];int lo = 0;int hi = a.length - 1;sort(a,lo,hi);}//对数组a中从索引lo到索引hi之间的元素进行排序private static void sort(Comparable[] a,int lo,int hi){//只有一个数据，不用排序了if (hi <= lo){return;}int mid = lo + (hi - lo) / 2;//对lo到mid之间的元素进行排序sort(a,lo,mid);//对mid + 1到hi之间的元素进行排序sort(a,mid + 1,hi);//对lo到mid这组数据和mid到hi这组数据进行归并merge(a,lo,mid,hi);}//从索引lo到所以mid为一个子组，从索引mid+1到索引hi为另一个子组，// 把数组a中的这两个子组的数据合并成一个有序的大组（从索引lo到索引hi）private static void merge(Comparable[] a,int lo,int mid,int hi){//lo到mid这组数据和mid + 1到hi这组数据归并到辅助数组assist对应的索引处int i = lo;//定义一个指针，指向assist数组中开始填充数据的索引int p1 = lo;//定义一个指针，指向第一组数据的第一个元素int p2 = mid + 1;//定义一个指针，指向第二组数据的第一个元素//比较左边小组和右边小组中的元素大小，哪个小，就把哪个数据填充到assist数组中while (p1 <= mid && p2 <= hi){if (less(a[p1],a[p2])){assist[i++] = a[p1++];}else {assist[i++] = a[p2++];}}//上面的循环结束后，如果退出循环的条件是p1 > mid，则证明左边小组中的数据已经归并完毕，// 如果退 出循环的条件是p2 > =hi,则证明右边小组的数据已经填充完毕；// 所以需要把未填充完毕的数据继续填充到assist中,// 下面两个循环，只会执行其中的一个while (p1 <= mid){assist[i++] = a[p1++];}while (p2 <= hi){assist[i++] = a[p2++];}//那么现在，assist数组中，从lo到hi的元素是有序的，再把数据拷贝到a数组中对应的索引处for (int index = lo; index <= hi ; index++) {a[index] = assist[index];}}//判断v是否小于wprivate static boolean less(Comparable v, Comparable w) {return v.compareTo(w) < 0;}//交换a数组中，索引i和索引j处的值private static void exchange(Comparable[] a, int i, int j) {Comparable temp = a[i];a[i] = a[j];a[j] = temp;}
}
