数据结构与算法-算法基础二

再来看一下二分查找，以及快速排序、堆排序

二分查找

 1     /**
 2      * 二分查找，每次只取中位数元素进行比较，这样比较的前提是序列有序
 3      */
 4     @org.junit.Test
 5     public void testBSearch() {
 6 
 7         int left = 0;
 8         int right = arr.length-1;
 9         for(;left<=right;) {
10             int middle = (left + right)/2;
11             if (arr[middle] > toSearch) {
12                 right = middle-1;
13             } else if (arr[middle] < toSearch) {
14                 left = middle+1;
15             }else {
16                 index = middle;
17                 break;
18             }
19         }
20     }

快速排序

快速排序的基本思想如下：

对数组进行随机化。
从数列中取出一个数作为中轴数(pivot)。
将比这个数大的数放到它的右边，小于或等于它的数放到它的左边。
再对左右区间重复第三步，直到各区间只有一个数。

特点：适合大量、无序的数据，不需要占用额外空间。

改进：

　　在区间较小时，可以转换为插入排序。

示例：

 1     /**
 2      * 快速排序，每轮排序都会确定一个元素的最终位置，并将其余元素放置在该元素两侧。
 3      */
 4     @org.junit.Test
 5     public void testQuick() {
 6         quick(arr, 0, arr.length-1);
 7     }
 8     private void quick(Integer[] arr, int left, int right) {
 9         if (left >= right) {
10             return;
11         }
12         int mid = split(arr, left, right);
13         quick(arr, left, mid-1);
14         quick(arr, mid+1, right);
15     }
16     private int split(Integer[] arr, int left, int right) {
17         int temp = arr[left];
18         for(;left<right;) {
19             for(;left<right&&arr[right]>=temp;right--) {
20             }
21             if (left < right) {
22                 arr[left++] = arr[right];
23             }
24             for(;left<right&&arr[left]<temp;left++) {
25             }
26             if (left < right) {
27                 arr[right--] = arr[left];
28             }
29         }
30         arr[left] = temp;
31         return left;
32     }

堆排序

大顶堆的定义：有n个元素的序列｛k1, k2, k3, ..., kn｝，满足k_i>=k_2i，k_i>=k_2i+1。

使用场景：优先队列（priority queue）。

大顶堆的构建：

　　插入元素时，需要自下而上筛选出最大元素至树根；

　　删除（树根）元素时，需要自上而下重新构建堆结构（首先要将右下角元素，即第n个元素，移至树根）。

使用数字表示一个大顶堆（形状上是一个完全二叉树）：

1         for(int i=n/2; i>=1; i--) {//构建大顶堆
2             adjust(toSort, i, n);
3         }
4         for(int i=1; i<n; i++) {//排序
5             int t = toSort[n-i+1];
6             toSort[n-i+1] = toSort[1];
7             toSort[1] = t;
8             adjust(toSort, 1, n-i);
9         }

 1     private void adjust(Integer[] arr, int parentIndex, int n) {
 2         int max = parentIndex;
 3         int sonIndex;
 4         for(;parentIndex*2<=n;) {
 5             if ((sonIndex=parentIndex * 2)<=n&&arr[sonIndex] != null && arr[max] < arr[sonIndex]) {
 6                 max = sonIndex;
 7             }
 8             if ((sonIndex=parentIndex * 2+1)<=n&&arr[sonIndex] != null && arr[max] < arr[sonIndex]) {
 9                 max = sonIndex;
10             }
11             if (max != parentIndex) {
12                 int t = arr[max];
13                 arr[max] = arr[parentIndex];
14                 arr[parentIndex] = t;
15                 parentIndex = max;
16             }else {
17                 break;
18             }
19         }
20     }