算法之快速排序

快速排序：顧名思義就是排序過程比較快的排序方法（在排序過程中交換時有可能位置跳躍比較大）。

快速排序的核心思想：找數組的中值，從前往後找第一個比中值的大的數，從後往前找第一個比中值小的數，找到後将它們倆交換位置，一輪結束後，将數組分成兩部分，繼續進行查找。

具體步驟：

（1）先給出一個無序數組，找到他的中值，從前往後找第一個比中值的大的數，從後往前找第一個比中值小的數，找到後将它們倆交換位置；

（2）判斷，若找到的這個大數位置和小數的位置都在中值處，或者大數位置在小數位置後面，則第一輪結束，将數組分為兩部分；

（3）否則将找到的這兩個數交換，接着給大數的位置+1，小數的位置-1；繼續重複上面的步驟；

（4）當第一輪結束後，将數組按照（startIndex,highIndex-1）（lowIndex+1,endIndex）分成兩部分，繼續重複上面的步驟直到将數排好序；

（5）将排好序的數組列印出來。

using System;
using System.Collections.Generic;
using System.Text;
namespace prjquicksort
{
class Program
{
static void Main(string[] args)
{
int[] ary = new int[] { 2, 8, 6, 5, 7, 1, 9 };//先準備一個無序數組
quicksort(ary, 0, ary.Length - 1);//調用quicksort函數
foreach (int x in ary)//用foreach函數列印排好序後的數組
{
Console.WriteLine(x);
}
}
static void quicksort(int []ary, int startIndex, int endIndex)//快速排序
{
//起始索引大于等于結束索引實數時，直接傳回。
if (startIndex>=endIndex)
{
return;
}
//中值等于起始索引加結束索引除2位置上的值。
int middle = ary[(startIndex + endIndex) / 2];
//比中指值大的數的索引（高位索引）初始化為起始索引。
int highIndex = startIndex;
//比中值小的數的索引（低位索引）初始化為結束索引。
int lowIndex = endIndex;
//排序次數不确定，多次排序後數組變成有序數組。
while (true)
{
//在數組中從高位索引到結束索引從前往後開始找第一個大于等于中值的數。
for (int i = highIndex; i <= endIndex; i++)
{
//如果找到了第一個大于等于中值的數，就将這個數的索引給高位索引，并跳出循環。
if (ary[i] >= middle)
{
highIndex = i;
break;
}
}
//在數組中從低位索引到起始索引從後往前開始找第一個小于等于中值的數。
for (int j = lowIndex; j >= startIndex; j--)
{
//如果找到了第一個小于等于中值的數，就将這個數的索引給低位索引，并跳出循環。
if (ary[j] <=middle)
{
lowIndex = j;
break;
}
}
//如果高位索引等于低位索引，則跳出循環。
if (highIndex == lowIndex)
{
break;
}
//如果高位索引大于低位索引，則跳出循環。
if (highIndex > lowIndex)
{
break;
}
//否則将找到的兩個數進行交換。
int temp = ary[highIndex];
ary[highIndex] = ary[lowIndex];
ary[lowIndex] = temp;
//下一次找的時候高位索引往後挪一位，低位索引往前挪一位。
highIndex++;
lowIndex--;
}
//将數組切成部分，第一部分從起始索引到高位索引-1；第二部分從低位索引+1到結束索引。
quicksort(ary, startIndex, highIndex - 1);
quicksort(ary, lowIndex + 1, endIndex);
}
}
}