黑马程序员技术交流社区

标题: 快速排序 [打印本页]

---

作者: 马毅    时间: 2012-12-14 00:45
标题: 快速排序


快速排序是一种效率很高的排序算法,合并排序是基于位置的,而快速排序是基于值的,
快速排序按照值对数组分区,先选定一个中值,把大于此值的放于一侧,小于的放于另一侧,接下来分别对两侧进行同样的操作,
最后得到一个排序好的数组,

以下是实现代码(采用的是将第一个元素作为中值):
(PS:不是我写的,我写的实现比这个要复杂,有些冗余,)

1. /// <summary>
   
2.         /// 快速排序
   
3.         /// </summary>
   
4.         /// <param name="arr">排序数组</param>
   
5.         /// <param name="low">数组的最低位</param>
   
6.         /// <param name="high">数组的最高位</param>
   
7.         /// 调用:
   
8.         ///int[] A = new int[] { 5, 3, 1, 9, 8, 2, 4, 7 };
   
9.         ///QuickSort(ref A, 0, A.Length - 1);
   
10.        static void QuickSort(ref int[] arr, int low, int high)
    
11.         {
    
12.             int midKey;
    
13.             if (low < high)
    
14.             {
    
15.                 midKey = Partition(ref arr, low, high);
    
16.                 QuickSort(ref arr, low, midKey - 1);
    
17.                 QuickSort(ref arr, midKey + 1, high);
    
18.             }
    
19.         }
    
20.         static int Partition(ref int[] arr, int low, int high)
    
21.         {
    
22. 
    
23.             int midKey = arr[low], keyValue = arr[low];
    
24. 
    
25.             while (low < high)
    
26.             {
    
27.                 while (low < high && arr[high] >= midKey)
    
28.                 {
    
29.                     --high;
    
30.                 }
    
31.                 arr[low] = arr[high];
    
32.                 while ( low < high && arr[low] <= midKey)
    
33.                 {
    
34.                     ++low;
    
35.                 }
    
36.                 arr[high] = arr[low];
    
37.             }
    
38. 
    
39.             arr[low] = keyValue;
    
40.             return low;
    
41.         }

复制代码

还有一种实现方式,是以数组最左边,最右边,和最中间的元素作为中值,而当数组较时采用更简单的排序,避免递归,只不过我写的还有些问题,若有实现代码,还请发出来,灰常感谢^_^
其他算法介绍

---

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

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