最近几年来，地理信息系统无论是在理论上还是应用上都处在一个飞速发展的阶段。 GIS被应用于多个领域的建模和决策支持，如城市管理、区划、环境整治等等，地理信息成为信息时代重要的组成部分之一； “数字地球”概念的提出，更进一步推动了作为其技术支撑的GIS的发展。 与此同时，一些学者致力于相关的理论研究，如空间感知、空间数据误差、空间关系的形式化等等。 这恰好说明了地理信息系统作为应用技术和学科的两个方面，并且这两个方面构成了相互促进的发展过程。
5.6.1. I. the concept and its introduction ¶
The two-way quick sort algorithm is an improved version of randomized quick sort. The partition process uses two index values (I, j) to traverse the array, setting the Time and space complexity are the same as randomized quick sorting. For arrays with a large number of repetitive elements, the efficiency of randomized quick sorting in the previous section is very low, resulting in extreme imbalance in the length of subarrays that are larger than or less than the base point data after partition, and even degenerate to O (n = 2) time complexity algorithms. In this case, two-way quick sorting algorithm can be used. Use two index values (I, j) to traverse our sequence, setting the <=v To the left of the location pointed to by index I, and set the >=v Is placed to the right of the location pointed to by index j, balancing the left and right subarrays 源码包下载： Download 5.6.2. II. Applicable instructions ¶
5.6.3. III. Process diagram ¶
5.6.4. 4. Java instance code ¶
QuickSort2Ways.java file code: ¶
package runoob; /*\* \* 双路快速排序 */ public class QuickSort2Ways { //核心代码---开始 private static int partition(Comparable[] arr, int l, int r){ // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot swap( arr, l , (int)(Math.random()\*(r-l+1))+l ); Comparable v = arr[l]; // arr[l+1...i) <= v; arr(j...r] >= v int i = l+1, j = r; while( true ){ while( i <= r && arr[i].compareTo(v) < 0 ) i ++; while( j >= l+1 && arr[j].compareTo(v) > 0 ) j --; if( i > j ) break; swap( arr, i, j ); i ++; j --; } swap(arr, l, j); return j; } //核心代码---结束 // 递归使用快速排序,对arr[l...r]的范围进行排序 private static void sort(Comparable[] arr, int l, int r){ if (l >= r) { return; } int p = partition(arr, l, r); sort(arr, l, p-1 ); sort(arr, p+1, r); } public static void sort(Comparable[] arr){ int n = arr.length; sort(arr, 0, n-1); } private static void swap(Object[] arr, int i, int j) { Object t = arr[i]; arr[i] = arr[j]; arr[j] = t; } // 测试 QuickSort public static void main(String[] args) { // 双路快速排序算法也是一个O(nlogn)复杂度的算法 // 可以在1秒之内轻松处理100万数量级的数据 // Quick Sort也是一个O(nlogn)复杂度的算法 // 可以在1秒之内轻松处理100万数量级的数据 int N = 1000000; Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000); sort(arr); SortTestHelper.printArray(arr); } }