算法
2018-04-07 本文已影响17人
激励上善若水
二分查找
public class TestBinarySearch {
private static final int[] arr = {0,1,2,3,4,5,6,7,8,9};
public static void main(String[] args) {
System.out.println(binarySearch(arr, 0, arr.length-1 , 3));
}
private static int binarySearch(int[] arr, int start, int end, int key){
if(start == end){
return -1;
}
final int mid = (end - start) / 2 + start;
if(key == arr[mid]){
return mid;
} else if(key < arr[mid]){
return binarySearch(arr, start, mid-1, key);
} else if(key > arr[mid]){
return binarySearch(arr, mid+1, end, key);
}
return -1;
}
}
冒泡排序
bubble-sort.gif
冒泡排序需要两个嵌套的循环. 其中, 外层循环移动游标; 内层循环遍历游标及之后(或之前)的元素, 通过两两交换的方式, 每次只确保该内循环结束位置排序正确, 然后内层循环周期结束, 交由外层循环往后(或前)移动游标, 随即开始下一轮内层循环, 以此类推, 直至循环结束.
static void bubbleSort(int[] array){
for (int i=array.length; i>0; i--) {
for(int j=0; j+1<i;j++){
if(array[j] > array[j+1]){
swap(array, j, j+1);
}
}
}
}
-
选择排序
Selection-Sort-Animation.gif
红色表示当前最小值，黄色表示已排序序列，蓝色表示当前位置
static void selectionSort(int[] arr){
for(int i=0; i<arr.length; i++){
int min = i;
for(int j=i+1; j<arr.length; j++){
if(arr[j] < arr[min]){
min = j;
}
}
if(min != i){
swap(arr, i, min);
}
}
}
- 从待排序序列中，找到关键字最小的元素；
- 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
注意要跟min去比较，因为每次循环min的值可能会变，不能跟i比较。
-
插入排序
Insertion-sort-example-300px.gif
直接插入排序的基本思想是：将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小，则交换，直到全部元素都比较过为止。
insert-sort.gif
static void insertionSort(int[] arr){
for(int i=0; i<arr.length-1; i++){
for(int j=i+1; j>0; j--){
if(arr[j] < arr[j-1]){
swap(arr, j, j-1);
}
}
}
}
注意：i<arr.length-1,因为j=i+1,否则无法访问到arr[j]
-
快速排序
基本思想
快速排序的基本思想：挖坑填数+分治法。
Sorting_quicksort_anim.gif
首先选一个轴值(pivot，也有叫基准的)，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
- 代码实现
①. i = L; j = R; 将基准数挖出形成第一个坑a[i]。
②．j--，由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
③．i++，由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
④．再重复执行②，③二步，直到i==j，将基准数填入a[i]中
递归版的快速排序：通过把基准temp插入到合适的位置来实现分治，并递归地对分治后的两个划分继续快排。那么非递归版的快排如何实现呢？
public static void main(String[] args) {
final int[] arr = {3,7,8,5,2,1,9,5,4};
quick(arr);
}
private static void print(int[] arr){
System.out.println();
for (int iterable_element : arr) {
System.out.print(iterable_element + " ");
}
}
/**
* 快速排序
*
* @param numbers
* 带排序数组
*/
public static void quick(int[] numbers) {
if (numbers.length > 0) {
quickSort(numbers, 0, numbers.length - 1);
}
}
/**
* 查找出中轴（默认是最低位low）的在numbers数组排序后所在位置
*
* @param numbers
* 带查找数组
* @param low
* 开始位置
* @param high
* 结束位置
* @return 中轴所在位置
*/
public static int getMiddle(int[] numbers, int low, int high) {
int temp = numbers[low]; // 数组的第一个作为中轴
while (low < high) {
while (low < high && numbers[high] >= temp) {
high--;
}
numbers[low] = numbers[high];// 比中轴小的记录移到低端
while (low < high && numbers[low] < temp) {
low++;
}
numbers[high] = numbers[low]; // 比中轴大的记录移到高端
}
numbers[low] = temp; // 中轴归位（此时应该是low=high）=》此时才是中轴真正应该所在的位置
print(numbers);
return low; // 返回中轴的位置
}
/**
*
* @param numbers 带排序数组
* @param low 开始位置
* @param high 结束位置
*/
public static void quickSort(int[] numbers,int low,int high) {
if(low < high) {
int middle = getMiddle(numbers,low,high);
quickSort(numbers, low, middle-1);
quickSort(numbers, middle+1, high);
}
}
