AS快速排序

快速排序算法

给出一个数组[3，1，5，3，7，9，8，10，43，11]

进行快速排序

第一步，两个指针，指向数组头部和尾部

第二步，选定参照对象，默认为头指针最初指向的元素的值，在这里，就是3

第三步，尾指针从尾部向前移动，知道找到小于参照值（3）的元素，停止移动

第四步，头指针，从头向尾移动，知道找到大于参照值（3）的元素，停止移动

注意：要先移动尾指针，再移动头指针，如果在头指针移动结束前，与尾指针相遇，则停止移动，交换序列第一个元素和头指针与尾指针共同指向的元素的值，交换完之后递归快排

第五步，若头指针和尾指针未相遇，则交换头指针与尾指针指向的元素的值，交换完之后，尾指针从当前位置继续向头指针移动，直到找到小于参照值（3）的元素或者与头指针相遇则停止移动，

若未相遇，则头指针从当前位置继续向尾部移动，直到找到大于参照值（3）或者与尾指针相遇，则停止移动。

如此循环，直至头尾指针相遇，交换头尾指针共同指向的元素的值与参照值，

交换完之后，以当前头尾指针指向元素为分界面，分成两个序列，递归调用上述排序步骤，直至不可拆分（长度为0或1），停止递归排序

上述序列的递归排序

第一步，头指针指向3，尾指针指向11

第二步，选定参照值，头指针指向的值（3）

第三步，尾指针从尾部向头部移动，指向1，停止移动，

第四步，头指针，从头向尾移动，移动到1时，与尾指针相遇，停止移动，交换参照值与头尾指针共同指向的元素的值，

得到[1,3,5,3,7,9,8,10,43,11]

以3为分界点，左边为1，不可拆分，停止递归

右边为[5,3,7,9,8,10,43,11]

递归排序，头尾指针分别指向5，11，

移动尾指针指向3，移动头指针，相遇，停止移动，交换参照值与头尾指针共同指向的元素的值

得到[3,5,7,9,8,10,43,11]

以5为分界点，得到左边序列[3]，右边序列[7，9，8，19，43，11]

左边不可再分，右边递归排序

AS代码实现如下

private var originalArr:Array = [4,3,5,1,7,9,8,0,1,22,12,30];

private function quickSort(left:int,right:int):void{

  if(left>=right){

  return;

}

var temp:int = originalArr[left];

var i:int = left;

var j:int = right;

var t:int;

while(i!=j){

  while(originalArr[j]>=temp&&i<j){

    j--;

}

  while(originalArr[i]<=temp&&i<j){

   i++;

 }

//头尾指针未相遇前找到合适的值，则交换头尾指针指向的值之后，继续从当前位置移动头尾指针

if(i<j){

  t = originalArr[i];

  originalArr[i] = originalArr[j];

  originalArr[j] = t;

}

}

//排完一次序列之后，基数归位，递归排序

originalArr[left] = originalArr[i];

originalArr[i] = temp;

quicksort(left,i-1);

quickSort(i+1,right);

}