- 浏览: 888537 次
- 性别:
- 来自: 武汉
文章分类
最新评论
-
小宇宙_WZY:
膜拜一下大神,解决了我一个大问题,非常感谢 orz
【解惑】深入jar包:从jar包中读取资源文件 -
JKL852qaz:
感谢,遇到相同的问题!
【解惑】深入jar包:从jar包中读取资源文件 -
lgh1992314:
为什么java中调用final方法是用invokevirtua ...
【解惑】Java动态绑定机制的内幕 -
鲁曼1991:
说的都有道理,protected只能被同一级包的类所调用
【解惑】真正理解了protected的作用范围 -
鲁曼1991:
...
【总结】String in Java
1、起泡排序 O(N^2)
起泡排序的过程很简单,首先将第一个关键字和第二个关键字比较,若为逆序,则将两个记录交换。然后再用第二个关键字和第三个关键字比较,以此类推,知道第n-1个关键字和第n个比较完,这样最大的关键字将被交换到第n个位置上。这个过程称做第一趟气泡排序。然后对前n-1进行第二趟气泡排序,将第二大的关键字交换到第n-1个位置上。当第n-1趟气泡排序完成之后,有序序列也就随之产生了。
#include<iostream.h> /************************** * 起泡排序 Bubble Sort * **************************/ class BubbleSort{ public: static void inc_sort(int keys[],int size); }; void BubbleSort :: inc_sort(int keys[], int size){ for(int i=size-1;i>=0;i--) for(int j=0;j<i;j++){ if(keys[j]>keys[j+1]){ int temp=keys[j]; keys[j]=keys[j+1]; keys[j+1]=temp; } } for(int k=0;k<size;k++) cout<<keys[k]<<" "; cout<<endl; } //Test BubbleSort void main(){ int raw[]={49,38,65,97,76,13,27,49}; int size=sizeof(raw)/sizeof(int); BubbleSort::inc_sort(raw,size); }
显然,气泡排序的时间复杂度为O(N^2),其空间复杂度为O(1) ,而且是稳定的 。
2、快速排序 O(N*logN)
快速排序是对起泡排序的一种改进。它的基本思想就是:通过一趟排序将待排记录分割成独立的两个部分,其中一个部分的关键字都比另一个部分关键字小,然后可以分别再对这两个部分继续快排,已达到整个序列有序。
具体的做法是:对待排序列keys[n]确定两个指针(low=0,high=n-1)。然后取第一个关键字keys[0]作为pivotkey(枢轴)。首先从high所指的位置起向前搜索找到第一个关键字小于pivotkey的记录,并将这个记录的关键字与pivotkey交换。然后从low所指的位置向后搜索,找到第一个关键字大于pivotkey的记录,并交换。轮流重复这两个步骤直到low=high位置。这样一个过程我们叫做一次快排(又叫一次划分)。
对划分后的序列的两个部分继续分别快排,知道所有序列有序位置,整个过程就是快排。
#include<iostream.h> class QuickSort{ private: //一次快排(划分) static int partition(int parts[],int low, int high); //快排 static void quick_sort(int parts[],int low, int high); public: //递增排序 static void inc_sort(int keys[],int size); }; int QuickSort :: partition(int parts[], int low, int high){ int pivotkey=parts[low]; //将第一个元素作为枢轴 while(low<high){ while(low<high && parts[high]>=pivotkey) --high; //将比枢轴小的关键字记录移动到低端 parts[low]=parts[high]; while(low<high && parts[low]<=pivotkey) ++low; //将比枢轴大的关键字记录移动到高端 parts[high]=parts[low]; } parts[low]=pivotkey; return low; //返回枢轴的位置 } void QuickSort :: quick_sort(int parts[],int low,int high){ if(low<high){ int pivotloc=QuickSort::partition(parts,low,high); QuickSort::quick_sort(parts,low,pivotloc-1); QuickSort::quick_sort(parts,pivotloc+1,high); } } void QuickSort :: inc_sort(int keys[],int size){ QuickSort::quick_sort(keys,0,size-1); for(int k=0;k<size;k++) cout<<keys[k]<<" "; cout<<endl; } void main(){ int raw[]={49,38,65,97,76,13,27,49}; int size=sizeof(raw)/sizeof(int); QuickSort::inc_sort(raw,size); }
//快速排序非递归算法 #include<iostream.h> #include<malloc.h> void quick_sort(int *pArr, int size){ int * beginIdxs=(int *)malloc(size * sizeof(int)); //记录待调整子序列的首地址 int * endIdxs=(int *)malloc(size * sizeof(int));//记录待调整子序列的尾地址 beginIdxs[0]=0; endIdxs[0]=size-1; int curIdx=0; while(curIdx>-1){ int low=beginIdxs[curIdx]; int high=endIdxs[curIdx]; int pivotkey=pArr[low]; //将第一个元素作为枢轴 while(low<high){ while(low<high && pivotkey<=pArr[high]) --high; pArr[low]=pArr[high]; while(low<high && pivotkey>=pArr[low]) ++low; pArr[high]=pArr[low]; } pArr[low]=pivotkey; int pivotidx=low; int begin=beginIdxs[curIdx]; int end=endIdxs[curIdx]; curIdx--; if(begin<pivotidx-1){ beginIdxs[++curIdx]=begin; endIdxs[curIdx]=pivotidx-1; } if(end>pivotidx+1){ beginIdxs[++curIdx]=pivotidx+1; endIdxs[curIdx]=end; } } //打印结果 for(int k=0;k<size;k++){ cout<<pArr[k]<<" "; } } void main(){ int raw[]={49,38,65,97,76,13,27,49}; int size=sizeof(raw)/sizeof(int); quick_sort(raw,size); }
快速排序的平均时间复杂度为O(N*logN) 。但快速排序在待排关键字序列有序或基本有序的情况下, 快速排序将蜕化成起泡排序,其 时间复杂度降为O(N^2) 。 经验证明,在所有O(N*logN)级的此类排序算法中,快速排序是目前被认为最好的一种内部排序方法。但是快排需要一个栈空间来实现递归。若每一趟划分都能够均匀的分割成长度相接近的两个子序列,则栈的最大深度为[logN]+1。因此空间复杂度为O(logN)。快排也是不稳定的。
快速排序有一个最坏的可能性,因此也就有很多优化来改进这个算法。
随机化快排:
快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取
第一个元素作为主元。这样在数组已经有序的情况下,每次划分将得到最坏的结果。一种比较
常见的优化方法是随机化算法,即随机选取一个元素作为主元。这种情
况下虽然最坏情况仍然是O(n^2),但最坏情况不再依赖于输入数据,而是由于随机函数取值不佳。
实际上,随机化快速排序得到理论最坏情况的可能性仅为
1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结:“随机化快速排序可
以满足一个人一辈子的人品需求。
”
随机化快速排序的唯一缺点在于,一旦输入数据中有很多的相同数据,随机化的效果将直
接减弱。对
于极限情况,即对于n个相同的数排序,随机化快速排序的时间复杂度将毫无疑问的降低到O(n^2)。
解决方法是用一种方法进行扫描,使没有交换的情况下主
元保留在原位置。
平衡快排(Balanced Quicksort) :每次尽可能地选择一个能够 代表中值的元素作为关键数据,然后遵循普通快排的原则进行比较、替换和递归。通常来说, 选择这个数据的方法是取开头、结尾、中间3个数据,通过比较选出其 中的中值。 取这3个值的好处是在实际问题(例如信息学竞赛……)中,出现近似顺序数据或逆序数据的概率较大,此时中间数据必然成为中值,而也是事实上的近 似中值。万一遇到正好中间大两边小(或反之)的数据,取的值都接近最值,那么由于至少能将两部分分开,实际效率也会有2倍左右的增加,而且利于将数据略微 打乱,破坏退化的结构。
对于快排优化的问题可以看看Java API(JDK)中的例子,参见《 java.util.Arrays的排序研究 》
发表评论
-
★经典问题—链表中的环问题
2010-06-29 14:43 4404转载:http://www.cppblog.com ... -
★经典问题—元素选择问题
2010-05-24 10:53 3307元素选择问题 : 给定线性序集中n个元素和一个整数k( ... -
【串和序列处理 8】最长平台问题
2010-04-28 16:41 36371、经典最长平台算法 已知一个已经从小到大 ... -
【排序结构7】 基数排序
2010-04-20 16:17 4514《桶排序 》中我们能够看到,数据值的范围越大,可能需要桶的个 ... -
【排序结构6】 桶排序
2010-04-19 20:28 22861从《基于比较的排序结构总结 》中我们知道:全依赖“比较”操作的 ... -
【排序结构5】 基于比较的内部排序总结
2010-04-18 16:15 6692★ 基于“比较”操作的内部排序性能大PK ... -
【排序结构4】 归并排序
2010-04-17 16:29 3266归并排序 O(N*logN) 是另一种效率很高的排序方法。&q ... -
【排序结构3】 选择排序
2010-04-14 21:10 3567(1) 简单选择排序 O(N^2) 一趟简单选择排序 ... -
【排序结构1】插入排序
2010-04-13 17:11 29791、基本概念介绍 (1) 如果待排序列中有两个 ... -
【串和序列处理 7】LIS 最长递增子序列
2010-03-25 16:37 5778LIS: 给定一个字符串序列S={x0,x1,x2,.. ... -
【串和序列处理 6】LCS 最长公共子序列
2010-03-23 17:38 8771LCS:又称 最长公共子序列。 其中子序列(subse ... -
【串和序列处理 5】KMP子串匹配算法
2010-03-22 19:59 9028模式匹配: 在字符串 ... -
★经典问题—欧几里得求最大公约数
2010-03-20 19:21 3328问题:快速求取正整数a,b的最大公约数? ... -
【串和序列处理 4】Suffix Trie 子串匹配结构
2010-03-20 15:15 9042Suffix Trie : 又称后 ... -
【串和序列处理 3】Trie Tree 串集合查找
2010-03-18 13:40 17570Trie 树, 又称字典树,单词查找树。它来源于retr ... -
【串和序列处理 2】字符串编辑距离算法
2010-03-15 08:45 11067我们来看一个实际应用。现代搜索技术的发展很多以提供优质、高效的 ... -
【串和序列处理 1】PAT Tree 子串匹配结构
2010-03-14 19:10 11258Patricia Tree 简称PAT tree ... -
【查找结构6】动态查找树比较
2010-03-12 13:32 11222我们这个专题介绍的动态查找树主要有: 二叉查找树(BST),平 ... -
【查找结构4】红黑树 [RBT]
2010-03-10 10:58 10511大部分转载:http://yanglongylj.blog.1 ... -
【查找结构5】多路查找树/B~树/B+树
2010-03-09 11:56 18108在前面专题中讲的BST、A ...
相关推荐
数据结构课程实验报告:交换排序-冒泡排序实验指导。
经典的数据结构 交换排序算法 非常实用 可以给初学者使用 也可以作为工具提供给编程人员
数据结构第23讲-插入排序2和交换排序-CPPT课件.ppt
本章主要介绍一些常用的排序算法:插入排序、交换排序、选择排序、归并排序和基数排序。这里介绍的排序算法都是基于待排序的数据元素序列构成的线性表采用顺序存储结构,即采用数组存储,并且默认为按关键字非递减...
数据结构排序插入排序和交换排序PPT学习教案.pptx
交换排序之冒泡排序.cpp
希尔排序法,最经典的排序法,但不是容易懂。包括希尔插入排序,希尔交换排序
数据结构课件:第10章 排序1插入排序和交换排序.pptx
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
数据结构的快速排序法!是基础的东西,望大家多多支持!
排序是计算机程序设计中的一种重要...插入排序类、交换排序类、选择排序类、归并排序类和基数排序类。算法主要包括:插入排序、折半插入排序、选择排序、冒泡排序、希尔排序、快速排序、堆排序、归并排序、基数排序等。
1排序的基本概念 2插入排序 3交换排序
冒泡排序,或许大家都知道,但是我当初直到大二才真正的理解。下载此档,就明白了。
插入排序、交换排序、选择排序、归并排序、基数排序 各种内排序方法的比较和选择
本资源比较全面的包涵了各种排序,三种交换排序,选择排序,桶排序,归并排序,快速排序,二分法排序,等等
数据结构-排序PPT课件.pptx
希尔排序 交换排序:冒泡排序,快速排序 选择排序:简单选择排序,堆排序
(2)统计每一种排序方法的性能(以上机运行程序所花费的时间为准进行对比),找出其中两种较快的方法; (3)统计每种算法所用的比较次数和交换次数,最后列表显示; (4)如果采用4种或4种以上的方法者,可适当...
使用MFC单文档实现数据结构8种排序算法的图形界面动态演示,更加形象的展示排序过程,八种排序算法包括插入排序(直接插入排序、折半插入排序、希尔排序)、选择排序(直接选择排序、堆排序)、交换排序(冒泡排序、...