黑马程序员技术交流社区

标题: 数组中快速排序算法 [打印本页]

---

作者: q757571446    时间: 2015-6-15 23:13
标题: 数组中快速排序算法
基础视频中学的数组排序是选择排序和冒泡排序，其实这两种算法的效率相对比较低下。在考虑最坏情况下，每次都需要遍历整个数组才能够确定一个最大值。而快速排序算法是直接取数组中的中间值，将比这个中间值大的放在中间值右边，比这个中间值小的放在左边。将一个数组分成两个部分，然后反复执行以上动作。例如：
通过反复递归就可以将一个数组排序正常

1.         public static void quickSort(int sortarray[], int lowIndex, int highIndex) {
   
2.                 int lo = lowIndex;// 记录最小索引
   
3.                 int hi = highIndex;// 记录最大索引
   
4.                 int mid;// 记录分界点元素
   
5.                 if (highIndex > lowIndex) {
   
6.                         mid = sortarray[(lowIndex + highIndex) / 2];// 确定中间分界点元素值
   
7.                         while (lo <= hi) {
   
8.                                 while ((lo < highIndex) && (sortarray[lo] < mid))
   
9.                                         ++lo;// 确定不大于分界元素值的最小索引
   
10.                                 while ((hi > lowIndex) && (sortarray[hi] > mid))
    
11.                                         --hi;// 确定大于分界元素值的最大索引
    
12.                                 if (lo <= hi) {// 如果最小与最大索引没有重叠
    
13.                                         swap(sortarray, lo, hi);// 交换两个索引的元素
    
14.                                         ++lo;// 递增最小索引
    
15.                                         --hi;// 递减最大索引
    
16.                                 }
    
17.                         }
    
18.                         if (lowIndex < hi)// 递归排序没有未分解元素
    
19.                                 quickSort(sortarray, lowIndex, hi);
    
20.                         if (lo < highIndex)// 递归排序没有未分解元素
    
21.                                 quickSort(sortarray, lo, highIndex);
    
22.                 }
    
23.         }
    
24.         public static void swap(int[] arr,int index_1,int index_2)
    
25.         {
    
26.                 int temp=arr[index_1];
    
27.                 arr[index_1]=arr[index_2];
    
28.                 arr[index_2]=temp;
    
29.         }

复制代码

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2