黑马程序员技术交流社区

标题: 麻烦师兄看看这段代码 [打印本页]

---

作者: s526349668    时间: 2014-7-6 16:46
标题: 麻烦师兄看看这段代码


这个是快速排序的代码，从if（key>array[j]就不理解了
private static void quickSort ( int[] array, int start, int end )
    {
        if (start < end)
        {
                //将赋值给key
            int key = array[start];
            int i = start;
            for ( int j = start + 1; j < end + 1; j++ )
            {
                if (key > array[j])
                {
                    int temp = array[j];
                    array[j] = array[i + 1];
                    array[i + 1] = temp;
                    i++;
                }
            }
            array[start] = array;
            array = key;
            quickSort (array, start, i - 1);
            quickSort (array, i + 1, end);
        }
    }

---

作者: 自闭宅男    时间: 2014-7-6 17:13
快速比较，然后位置调换

---

作者: fantacyleo    时间: 2014-7-6 18:40


这段快排代码思路不是很清晰。我觉得比较好理解的快排思路是这样的：

在待排序数组中选一个数作为key，一般选数组首元素。然后通过交换，让数组变成这样：key元素左边的元素都小于key，key元素右边的元素都大于等于key。接下来对key左右的两个子数组分别排序就可以了。图示如下：



实现代码：

1. void quickSort(int[] arr, int start, int end) {
   
2. 
   
3.     if(start >= end)
   
4.         return;
   
5. 
   
6.     int key = arr[start];
   
7.     int i = start, j = end;
   
8. 
   
9.     while(true) {
   
10. 
    
11.         // 从尾部开始找到一个小于key的元素
    
12.         while(i < j && arr[j] >= key)
    
13.             j--;
    
14. 
    
15.         // 从头部开始找到一个大于或等于key的元素
    
16.         while(i < j && arr[++i] < key)
    
17.             ;
    
18. 
    
19.         // 交换这两个数
    
20.         swap(arr, i, j);
    
21. 
    
22.         // i,j相遇，查找结束
    
23.         if(i == j)
    
24.             break;
    
25. 
    
26. 
    
27.     }
    
28. 
    
29.     // key左边的元素都小于key，key右边的元素都大于或等于key
    
30.     swap(arr, start, j);
    
31. 
    
32.     // 排序key左右两个子数组
    
33.     quickSort(arr, start, j - 1);
    
34.     quickSort(arr, j + 1, end);
    
35. 
    
36. 
    
37. }
    

复制代码

---

作者: s526349668    时间: 2014-7-6 19:15

fantacyleo 发表于 2014-7-6 18:40
这段快排代码思路不是很清晰。我觉得比较好理解的快排思路是这样的：

在待排序数组中选一个数作为key，一 ...

太感谢了啊

---

作者: fantacyleo    时间: 2014-7-6 19:27

s526349668 发表于 2014-7-6 19:15
太感谢了啊

把帖子状态改成”提问结束“吧，这样就可以向版主求技术分了:lol

---

作者: android0276    时间: 2014-7-6 19:43
java直接调类排序啊。

---

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

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