快速排序算法

今天我们讲解快速排序

还是老规矩，先列一下快速排序的规则：

1）设置两个变量font、end，排序开始的时候：font=0，end=N-1；　　

2）以第一个数组元素作为关键数据，赋值给key，即 key=array[0]；　　

3）从font开始向后搜索，即由前开始向后搜索（++font），找到第一个大于key的值array[font](这里注意，我们用的是++font，就是为了找到大于key的这个font值，如果用font++的话，最后使用时应该用font+1)；　　

4） 从end开始向前搜索，即由后开始向前搜索（--end），找到第一个小于key的array[end]，在3)与4)的过程中如果 font>=end的时候搜索结束，如果font<end时就可以交换array[font]和array[end]值；　　

5）重复第3、4、5步，直到 font>=end结束循环。

下面是今天的代码：

publicstaticvoid Quick(int[] array, int font, int end)
        {
            　　if (font < end)
            　　{
                　　　　int i = font -1;
                　　　　int j = end +1;
                　　　　int key = array[(i + j) /2];
                　　while (true)
                　　{
                    　　　　while (array[++i] < key) ;//这里是步骤3)
　　　　while (array[--j] > key) ;//这里是步骤3)
　　if (i < j)
                    　　{
                        　　　　int temp = array[i];
                        　　　　array[i] = array[j];
                        　　　　array[j] = temp;
                    　　}
                    　　else
                    　　{
                        　　　　break;
                    　　}

                }
                ////这里要注意，这里是我们程序最关键的地方：运行到这里我们就要递归我们的这个方法，
//这里我们可以看到0～i-1的/这一段中都是小于key值的，i-1就是key值的索引，i-1～end
                //这一段都是大于key值的。然后继续查找小于key值和大于key值的快速排序。
                　　Quick(array, font, i -1);
                　　Quick(array, j +1, end);
            　　}
        }

//方法二

function quick_sort($array) { 
	　　if (count($array) <= 1) 
		　　　　return $array; 
	　　$key = $array[0]; 
	　　$left_arr = array(); 
	　　$right_arr = array(); 
	　　for ($i=1; $i<count($array); $i++){ 
		　　　　if ($array[$i] <= $key) 
			　　　　　　$left_arr[] = $array[$i]; 
		　　　　else 
			　　　　　　$right_arr[] = $array[$i]; 
	　　} 
	　　$left_arr = quick_sort($left_arr); 
	　　$right_arr = quick_sort($right_arr); 
	　　return array_merge($left_arr, array($key), $right_arr); 
}