Python实现快速排序--数据结构

时间:2023-03-09 06:45:38
Python实现快速排序--数据结构

快速排序(Quick Sort)

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序n个元素要O(nlogn)次比较。在最坏状况下则需要O(n^2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他O(nlogn)算法更快,因为它的内部循环可以在大部分的架构上很有效率地被实现出来。

  快速排序使用分治策略(Divide and Conquer)来把一个序列分为两个子序列。步骤为:

  1. 从序列中挑出一个元素,作为"基准"(pivot).一般使用第一个元素或最后一个元素作为比较的基准。
  2. 把所有比基准值小的元素放在基准前面,所有比基准值大的元素放在基准的后面(相同的数可以到任一边),这个称为分区(partition)操作。
  3. 对每个分区递归地进行步骤1~2.

Python代码:

def Partition(seq,left,right):
key=seq[right]
tail=left-
for i in range(left,right):
if seq[i]<=key:
tail+=
if tail!=i:
seq[tail],seq[i]=seq[i],seq[tail]
seq[tail+],seq[right]=seq[right],seq[tail+]
return tail+
def QuickSort(seq,left,right):
if left>=right:
return
index=Partition(seq,left,right)
QuickSort(seq,left,index-)
QuickSort(seq,index+,right)
return seq s = [, , , , , , , , , , , , ]
print("before sort:",s)
s1 = QuickSort(s, left = , right = len(s) - )
print("after sort:",s1)

本文将要实现快排的一种思路如下:

第一个函数Partition()的作用是:给定一个序列和序列的起始位置和末尾元素的位置,以末尾元素为基准,将小于基准的数据放在基准的左边,大于基准的数据放在右边,最后返回基准数据的索引下标

第二个函数QuickSort()的作用是不断的递归循环,直到出现left>=right的情况结束

其中,最难理解的是Partition函数。在这里做如下解释:

例如一组数据:s = [6, 8, 1, 4, 3, 9, 5, 4, 11, 2, 2, 15, 7],n=siezof(s)

第一步:以序列的最后一个元素作为基准,pivot=7

第二步:从左到右遍历前n-1个元素,这里先借助一个辅助变量tail,tail的作用是作为一个索引,用来表示遍历过程中,所有比基准小的数组成的子序列中的最后一个元素的索引。特别绕!例如遍历s,一个元素6要比pivot=7小,所以子序列为[6],tail值为0,然后继续向前遍历,第二个元素8比pivot大,跳过,遍历第三个元素1要比pivot小,那么子序列为[6,1],tail值为2,遍历第四个元素4要比pivot小,那么子序列为[6,1,4],tail值为3,.。。。最后tail+1即为pivot=7在原序列中的位置。

C代码:摘自:http://www.cnblogs.com/eniac12/p/5329396.html

#include <stdio.h>

void Swap(int A[], int i, int j)
{
int temp = A[i];
A[i] = A[j];
A[j] = temp;
} int Partition(int A[], int left, int right) // 划分函数
{
int pivot = A[right]; // 这里每次都选择最后一个元素作为基准
int tail = left - ; // tail为小于基准的子数组最后一个元素的索引
for (int i = left; i < right; i++) // 遍历基准以外的其他元素
{
if (A[i] <= pivot) // 把小于等于基准的元素放到前一个子数组末尾
{
Swap(A, ++tail, i);
}
}
Swap(A, tail + , right); // 最后把基准放到前一个子数组的后边,剩下的子数组既是大于基准的子数组
// 该操作很有可能把后面元素的稳定性打乱,所以快速排序是不稳定的排序算法
return tail + ; // 返回基准的索引
} void QuickSort(int A[], int left, int right)
{
if (left >= right)
return;
int pivot_index = Partition(A, left, right); // 基准的索引
QuickSort(A, left, pivot_index - );
QuickSort(A, pivot_index + , right);
} int main()
{
int A[] = { , , , , , , , , }; // 从小到大快速排序
int n = sizeof(A) / sizeof(int);
QuickSort(A, , n - );
printf("快速排序结果:");
for (int i = ; i < n; i++)
{
printf("%d ", A[i]);
}
printf("\n");
return ;
}