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

原理不想说了，都是老生常谈。 我的理解就是：  每次遍历一次的时候 把大的放到右边，小的放到左边，再从这个中间值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         {
            while( i= key ) //小的放到左边
           {
               j--
           }
           if( i            {
               temp[i++]  = temp[j]
           }
          while(i           {
              i++
          }
          if( i           {
              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

    local key = tempArr[left];

    local i= left;

    local j =right

    while i < j  do

    while i= key   do --从右到左 目的是吧小的值放到左边 找到一个就可以了

           j = j-1;

       end

       if i

           tempArr[i] =  tempArr[j]

           i = i+1;

       end

       while i

           i = i+ 1;

       end

       if i

            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");