Python快速排序算法實(shí)例分析

2020-01-04 16:14:07

字體：大中小

供稿：網(wǎng)友

本文實(shí)例講述了Python快速排序算法。分享給大家供大家參考，具體如下：

快速排序的時(shí)間復(fù)雜度是O(NlogN)

算法描述：

① 先從序列中取出一個(gè)數(shù)作為基準(zhǔn)數(shù)
② 分區(qū)過(guò)程, 將比這個(gè)數(shù)大的數(shù)全部放到它的右邊, 小于或等于它的數(shù)全部放到它的左邊
③ 再對(duì)左右區(qū)間重復(fù)第二步, 直到各區(qū)間只有一個(gè)數(shù)

假設(shè)對(duì) 6, 1, 2, 7, 9, 3, 4, 5, 10, 8 進(jìn)行排序, 首先在這個(gè)序列中隨便找一個(gè)基準(zhǔn)數(shù)(用來(lái)參照), 比如選擇 6 為基準(zhǔn)數(shù), 接下來(lái)把所有比基準(zhǔn)數(shù)大的數(shù)放在6的右邊, 比6小的數(shù)放在左邊

原理分析:

① 選擇最左邊的數(shù)為基準(zhǔn)數(shù)key
② 設(shè)立兩個(gè)游標(biāo) low 和 high , 分別指向數(shù)組的最低位和最高位
③ 然后high先動(dòng), 如果high位上的數(shù)比key大, 則向前走, 如果high-1位上的數(shù)比key大, 繼續(xù)向前走, 直到該位上的數(shù)<=key
④ 此時(shí)比較low位, 如果<=key, low向后走, 變?yōu)閘ow+1, 依次類推, 直到該位上的數(shù)比key大
⑤ 交換high和low位上的數(shù)
⑥ 重復(fù)以上步驟, 直到low=high , 交換 key 和 high 位上的值
⑦ 最后進(jìn)行遞歸操作

示例代碼：

#!/usr/bin/env python# coding:utf-8# 設(shè)置最低位和最高位def quickSort(nums, low, high):  # 設(shè)置一個(gè)比較基準(zhǔn)key  key = nums[low]  while low<high:    # 如果最高位的數(shù) 大于等于 key則向前走    while low<high and nums[high] >= key:      high -= 1    # 如果最低位的數(shù) 小于等于 key則向后走    while low<high and nums[low] <= key:      low += 1    # 交換值    nums[low], nums[high] = nums[high], nums[low]  #最后low=high, 此時(shí)交換key和high位上的值, 使小于key的值在key左邊, 大的在key右邊  nums[nums.index(key)], nums[low] = nums[low], nums[nums.index(key)]  # 返回最低位的位置  return low# 進(jìn)行重復(fù)操作def interval(nums, low, high):  if low<high:    # 進(jìn)行排序并得到最低位位置以循環(huán)操作    key_index = quickSort(nums, low, high)    interval(nums, low, key_index)    interval(nums, key_index+1, high)nums = [64,3,9,2,4,7,0,12,45,]interval(nums, 0, len(nums)-1)print "VEVB武林網(wǎng)測(cè)試結(jié)果："print nums"""[0, 2, 3, 4, 7, 9, 12, 45, 64]"""

運(yùn)行結(jié)果：

Python,快速排序,算法