基础视频中学的数组排序是选择排序和冒泡排序,其实这两种算法的效率相对比较低下。在考虑最坏情况下,每次都需要遍历整个数组才能够确定一个最大值。而快速排序算法是直接取数组中的中间值,将比这个中间值大的放在中间值右边,比这个中间值小的放在左边。将一个数组分成两个部分,然后反复执行以上动作。例如:
通过反复递归就可以将一个数组排序正常- public static void quickSort(int sortarray[], int lowIndex, int highIndex) {
- int lo = lowIndex;// 记录最小索引
- int hi = highIndex;// 记录最大索引
- int mid;// 记录分界点元素
- if (highIndex > lowIndex) {
- mid = sortarray[(lowIndex + highIndex) / 2];// 确定中间分界点元素值
- while (lo <= hi) {
- while ((lo < highIndex) && (sortarray[lo] < mid))
- ++lo;// 确定不大于分界元素值的最小索引
- while ((hi > lowIndex) && (sortarray[hi] > mid))
- --hi;// 确定大于分界元素值的最大索引
- if (lo <= hi) {// 如果最小与最大索引没有重叠
- swap(sortarray, lo, hi);// 交换两个索引的元素
- ++lo;// 递增最小索引
- --hi;// 递减最大索引
- }
- }
- if (lowIndex < hi)// 递归排序没有未分解元素
- quickSort(sortarray, lowIndex, hi);
- if (lo < highIndex)// 递归排序没有未分解元素
- quickSort(sortarray, lo, highIndex);
- }
- }
- public static void swap(int[] arr,int index_1,int index_2)
- {
- int temp=arr[index_1];
- arr[index_1]=arr[index_2];
- arr[index_2]=temp;
- }
复制代码
|
|