极快排序 TypeScript C++ lua 实现 分治法(Divide-and-ConquerMethod)。 效率 O(N*logN)

原理不想说了，都是老生常谈。 我的理解就是：  每次遍历一次的时候 把大的放到右边，小的放到左边，再从这个中间值Key开始 再查一次左边的 和 右边的 。 递归的用法而已。 

TypeScript

var arry:number[] = [2,9,3,5,4,6,7,8,1]
console.log(arry)
function quickSort( temp:number[] ,left: number,right: number) {  

    if( left < right)
    {
        var  key : number = temp[left];
        var  i : number = left
        var  j : number = right
        while( i<j  )
        {
            while( i<j && temp[j] >= key ) //小的放到左边
           {
               j--
           }
           if( i<j)
           {
               temp[i ]  = temp[j]
           }
          while(i<j && temp[i]  < key )
          {
              i
          }
          if( i<j)
          {
              temp[j--]  = temp[i]
          }

        }
        temp[i] = key 
        console.log(arry)
        quickSort(temp,left,i-1)
        quickSort(temp,i 1,right)
    }  
} 
quickSort(arry,0,8);
console.log(arry)

C

int a[] = { 2,9,3,5,4,6,7,8,1};
    this->stepA(a,0,8);
void  HttpConfigArrangeAdvertisementForInserAD::stepA(int arr[], int  left, int right )
{
    if (left < right) {
        int key = arr[left];
        int i = left;
        int j = right;
        while (i < j)
       {  
            while (i < j && arr[j] >= key) // 从右向左找第一个小于key的数
            {
                j--;
            }
            if (i < j)
            {
                arr[i ] = arr[j];
            }
            while (i < j && arr[i] < key) // 从左向右找第一个大于等于key的数
            {
                i ;
            }
            if (i < j)
            {
                arr[j--] = arr[i];
            }
        }
        arr[i] = key;      //退出时，i等于j。将key填到这个坑中。
        stepA(arr, left, i- 1);
        stepA(arr, i 1, right);
    }

Lua

  local arr= { 2,9,3,5,4,6,7,8,1};

    dump(arr,"排序前372 ");

    local function quickSort(tempArr,left ,right )

    if left<right then

    local key = tempArr[left];

    local i= left;

    local j =right

    while i < j  do

    while i<j and  tempArr[right] >= key   do --从右到左 目的是吧小的值放到左边 找到一个就可以了

           j = j-1;

       end

       if i<j then

           tempArr[i] =  tempArr[j]

           i = i 1;

       end

       while i<j   and  tempArr[i] < key   do  --从左到右，目的把大的值放到右边 找到一个就可以了

           i = i 1;

       end

       if i<j then

            tempArr[j] =    tempArr[i]

            j = j-1;

       end

    end

    tempArr[i]  = key

    quickSort(tempArr,left, i-1 );

    quickSort(tempArr,i 1, right );

    end

    end

    quickSort(arr, 1,9 );

    dump(arr,"排序后 378");

这篇好文章是转载于：学新通技术网