Python 快速排序法(转)

方法解读:

例:对初始序列:“6  1  2 7  9  3  4  5 10  8”采用快速排序法:

一、分别从初始序列“6  1  2 7  9  3  4  5 10  8”两端开始“探测”。

从右往左找一个小于6的数,再从左往右找一个大于6的数,然后交换他们

这里可以用两个变量 i j ,分别指向序列最左边和最右边。

我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。

刚开始的时候让 哨兵i 指向序列的最左边(即i=1),指向数字6

让 哨兵j 指向序列的最右边(即j=10),指向数字8

 二、首先 哨兵j 开始出动。

因为此处设置的基准数是最左边的数,所以需要让哨兵j先出动,这一点非常重要(请自己想一想为什么)。

哨兵j 一步一步地向左挪动(即 j–),直到找到一个小于6的数停下来。

接下来 哨兵i 再一步一步向右挪动(即 i++),直到找到一个数大于6的数停下来。

最后 哨兵j 停在了数字5面前,哨兵i 停在了数字7面前。

现在交换 哨兵i哨兵j 所指向的元素的值。

到此,第一次交换结束。

三、接下来开始 哨兵j 继续向左挪动(再友情提醒,每次必须是 哨兵j 先出发)。

他发现了4(比基准数6要小,满足要求)之后停了下来。

哨兵i 也继续向右挪动的,他发现了9(比基准数6要大,满足要求)之后停了下来。

此时再次进行交换。

四、第二次交换结束,“探测”继续。
哨兵j 继续向左挪动,他发现了3(比基准数6要小,满足要求)之后又停了下来。
哨兵i 继续向右移动,糟啦!此时 哨兵i哨兵j 相遇了,哨兵i哨兵j 都走到3面前。
说明此时“探测”结束。
我们将基准数6和3进行交换。交换之后的序列如下。

五、  到此第一轮“探测”真正结束。

此时以基准数6为分界点,6左边的数都小于等于6,6右边的数都大于等于6。

回顾一下刚才的过程,其实 哨兵j 的使命就是要找小于基准数的数,而 哨兵i 的使命就是要找大于基准数的数,直到 i j 碰头为止。

现在基准数6已经归位,它正好处在序列的第6位。
此时我们已经将原来的序列,以6为分界点拆分成了两个序列,左边的序列是“3  1 2  5  4”,右边的序列是“9  7  10  8”。
接下来还需要分别处理这两个序列。因为6左边和右边的序列目前都还是很混乱的。
不过不要紧,我们已经掌握了方法,接下来只要模拟刚才的方法分别处理6左边和右边的序列即可。
六、现在先来处理6左边的序列现吧。
左边的序列是“3  1  2 5  4”。请将这个序列以3为基准数进行调整,使得3左边的数都小于等于3,3右边的数都大于等于3。好了开始动笔吧。
如果你模拟的没有错,调整完毕之后的序列的顺序应该是。
        2  1  3  5  4
 OK,现在3已经归位。
接下来需要处理3左边的序列“2 1”和右边的序列“5 4”。
对序列“2 1”以2为基准数进行调整,处理完毕之后的序列为“1 2”,到此2已经归位。
序列“1”只有一个数,也不需要进行任何处理。至此我们对序列“2 1”已全部处理完毕,得到序列是“1 2”。
序列“5 4”的处理也仿照此方法,最后得到的序列如下。
        1  2  3 4  5  6 9  7  10  8
七、对于序列“9  7  10  8”也模拟刚才的过程,直到不可拆分出新的子序列为止。
最终将会得到这样的序列,如下。
        1  2  3 4  5  6  7  8 9  10
八、到此,排序完全结束。
细心的同学可能已经发现,快速排序的每一轮处理其实就是将这一轮的基准数归位,直到所有的数都归位为止,排序就结束了。
下面上个霸气的图来描述下整个算法的处理过程。

九、原始网址:https://blog.csdn.net/adusts/article/details/80882649

十、Python程序:

#快速排序法:

def quickSort(arr,left,right):#arr:待排序的数列;left:数列开始的下标索引;right:数列结束的下标索引

  if left > right:#如果开始索引大于结束索引
    return

  temp=arr[left];#取最左边的数为 基准数
  i,j=left,right

  while i!= j:#现从右边开始找
    while arr[j]>=temp and i<j:#当前数值大于基准数
      j-=1

    while arr[i]<=temp and i<j:#当前数值小于基准数
      i+=1

    if i<j:#交换两个数再数组中的位置
      t=arr[i]
      arr[i]=arr[j]
      arr[j]=t

  #将 基准数 归位
  arr[left]=arr[i]
  arr[i]=temp

  quickSort(arr,left,i-1)#递归:继续处理左边的
  quickSort(arr,i+1,right)#递归:继续处理右边的

#测试
arr=[10,7,8,8,9,1,5]
n=len(arr)
quickSort(arr,0,n-1)
print(“排序后的数组:”)
for i in range(n):
print(“%d” %arr[i])