关注码农话题
做一个实实在在的内行人

快速排序

快速排序是一种高效的排序算法,并基于分割数据的数组成更小的数组。一个大的数组被划分成两个数组,其中一个保持值比规定的值小的表示基于支点在其上的分区是由与另一个数组保存值大于支点的值。

快速排序分割数组,然后调用自身递归两次排序得到的两个子数组。该算法对大型数据集作为平均和最坏情况的复杂性相当有效率为O(nlogn),其中n是项目的数目。

Quick Sort Partition Animation

伪代码

A : array of items 

procedure quickSort(left, right)
   if right-left <= 0
      return
   else     
      pivot = A[right]
      partition = partitionFunc(left, right, pivot)
      quickSort(left,partition-1)
      quickSort(partition+1,right)    
   end if		
end procedure

function partitionFunc(left, right, pivot)
   leftTutorialser = left -1
   rightTutorialser = right

   while True do
      while A[++leftTutorialser] < pivot do
         //donothing            
      end while
		
      while rightTutorialser > 0 && A[--rightTutorialser] > pivot do
         //donothing         
      end while
		
      if leftTutorialser >= rightTutorialser
         break
      else                
         swap leftTutorialser,rightTutorialser
      end if
		
   end while      
   swap leftTutorialser,right
   return leftTutorialser
end function

procedure swap (num1, num2)
   temp = A[num1]
   A[num1] = A[num2]
   A[num2] = temp;
end procedure

入职你的梦想 VS 变现你的技术

IT面试宝典码农市场