| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 466 人关注过本帖
标题:快速排序(QuickSort)
只看楼主 加入收藏
asdgzw1
Rank: 1
等 级:新手上路
帖 子:9
专家分:0
注 册:2013-6-20
结帖率:100%
收藏
 问题点数:0 回复次数:0 
快速排序(QuickSort)
  基于树的算法的堆排序是广泛使用的原地数组排序。但快速排序的性能甚至超过了堆排序。这是已知最快的排序方法。

  快速排序使用分割法对表进行排序,将数组内元素分割成若干部分。

  【算法原理】快速排序的独创之处在于两个索引在扫描表期间的交互作用。scanUp往表的高端(右)移动,寻找比中心值大的元素,一旦找到扫描终止,准备将元素重新放置到高端子表中,而scanDown则往表的低端(左)移动,寻找蔽中心值小的元素,这样两个子表中各有一个错位元素,因而可以将其进行交换swap(a[scanUp],A[scanDown])。scanUp和scanDown擦肩而过时,我们找到2个表之间的分割点并求出中心值的最后位置swap(a[0],A[scanDown])。

  



  QuickSort算法:

  pivot=A[mid]; //mid=(high+low)/2

  scanUp=low+1 指向表头,scanDown=high 指向表尾

  //scanUp<=scanDown 且所指向的元素A[scanUp]<=pivot.

  while(scanUp<=scanDown && A[scanUp]<= pivot)

  { scanUp++; //往表尾移动

  }

  //pivot

  while(pivot

  {scanDown--; //往表头移动

  }

  if(scanUp

  { Swap(A[scanUp],A[scanDown]); //交换错位元素

  }else

  { return;}

  QuickSort使用递归处理子表。分割后:[low,mid-1][mid][mid+1,high],终止条件:子表元素个数<2

  (单元素表或空表必然有序)

  void QuickSort(T A[],int low, int high)

  { T pivot; //中心值

  int scanUp,scanDown; //上游标、下游标

  int mid;//中心索引

  if(high-low<=0) //如果表元素个数小于2个,则返回

  {return;}

  else

  { if(high-low ==1) //如果子表有2个元素,对其进行比较,并在必要时进行交换

  { if(A[high]

  {Swap(A[low],A[high]); }

  return;

  }

  mid=(low+high)/2; //定义中心索引

  pivot=A[mid]; //中心值赋值给pivot

  Swap(A[mid],A[low]); //交换pivot及低端元素的值

  //初始化扫描索引scanUp,scanDown

  scanUp=low+1;

  scanDown=high;

  //定位错位元素;当scanDown

  do

  { while(scanUp<=scanDown && A[scanUp]<=pivot)

  scanUp++;

  while(piovat

  scanDown--;

  if(scanUp < scanDown)

  { Swap(A[scanUp],A[scanDown]); //交换错位元素

  }

  }while(scanUp>scanDown);

  //将pivot拷贝到scanDown位置,分开两个子表

  A[low]=A[scanDown];

  A[scanDown]=pivot;

  //若低端子表(low,scanDown-1)有2个或更多个元素,则进行递归调用

  if(low < scanDown-1)

  QuickSort(A,low,scanDown-1);

  //若高端子表(scanDown+1,high)有2个或更多个元素,则进行递归调用

  if(scanDown+1

  QuickSort(A,scanDown+1,high);

  }

  }

  最好情况:已升序排列的数组

  其次:已降序排列的数组

  最坏情况:中心值总是子表中的最小元素。此种情况下性能不比选择排序或插入排序更好,但现实中不太可能发生。

  



  



  各种排序算法性能比较:

  (1)O(n的2次方)量级排序算法比较:

  快速排序(QuickSort) > 插入排序(InsertionSort) > 选择排序(SelectionSort) > 交换排序(ExchangeSort) > 冒泡排序(BubbleSort)

  (2)O(nlog2n)量级排序算法比较:

  快速排序(QuickSort) > 堆排序(HeapSort) > 竞赛排序(TournamentSort) > 树排序(TreeSort)

  3.哈希法(Hashing)

  键值对提供对数据的访问,但大多数并不作为数组记录的索引。在多数应用中,键用来提供对数据的间接引用。用一个函数将键映射到一定的整数范围内,然后用整数值来访问数据,被称为"哈希函数(hash function)",映射到某个与哈希函数相关联的表,其索引范围是0~n-1,此表被称为"哈希表(hash table)",它存放数据或数据的引用。
编辑澳门娱乐城:http://www.
搜索更多相关主题的帖子: 元素 中心 
2013-06-22 14:11
快速回复:快速排序(QuickSort)
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.027912 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved