- 浏览: 955468 次
- 性别:
- 来自: 魔都
文章分类
- 全部博客 (745)
- MultiThread (19)
- My Plan (118)
- JavaBasic (61)
- MyInterview (104)
- InternetTechnique (5)
- ProjectConclusion (1)
- Maven (5)
- MogoDb (5)
- Hadoop (11)
- Memcached (6)
- TechniqueCollect (1)
- Ibaits (1)
- Android (34)
- ItLife (40)
- Tree (2)
- ProjectArchitect (7)
- Open Source (3)
- liunx (5)
- socket (8)
- Spring (27)
- DesginPattern (35)
- WebBasic (13)
- English (13)
- structs (1)
- structs2 (2)
- Oracle (17)
- Hibernate (2)
- JavaScript (4)
- Jdbc (1)
- Jvm (15)
- Ibatis (1)
- DataStructures (13)
- Https/Socket/Tcp/Ip (3)
- Linux (4)
- Webservice (7)
- Io (2)
- Svn (1)
- Css (1)
- Ajax (1)
- ExtJs (1)
- UML (2)
- DataBase (6)
- BankTechnique (3)
- SpringMvc (3)
- Nio (3)
- Load Balancing/Cluster (3)
- Tools (1)
- javaPerformanceOptimization (8)
- Lucene(SEO) (1)
- My Think (80)
- NodeJs (1)
- Quartz (1)
- Distributed-java (1)
- MySql (7)
- Project (4)
- junit (4)
- framework (1)
- enCache (1)
- git (2)
- SCJP (1)
- sd (1)
最新评论
-
lkjxshi:
你都这水平了还考这个证干嘛
SCJP 认证考试指南 -
钟逸华:
问的真多
百度java开发面试题(转) -
zuimeitulip:
觉得我就是这样的,从小阅读量就很少,导致现在的读的速度非常慢, ...
让读书成为一种习惯 -
DDT_123456:
我觉得你是不符合要求。问你hashmap的那个问题,你那样回答 ...
阿里面试2(转) -
jingjing0907:
刚刚写了很多读过此博客的感受,竟然没有发上去,以为我注册账号还 ...
让读书成为一种习惯
算法之排序
十三个经典算法研究与总结、目录+索引
http://blog.csdn.net/v_july_v/article/details/6305212
排序的一些概念
稳定性和不稳定性:关键字相等的记录在排序情况不唯一。
内排序和外排序:简单来说前者的操作都是在内存中,后者数据太多,存在于外部存储设备的交互操作。
一般我们说的的算法都是值指的内排序。
对于排序的分类可能有好几种:
一般按操作方式和思想可分为:交换,插入,选择,合并等。
也有按计算复杂度的来分的,O(n^2)简单排序(冒泡,简单选折,直接插入)和改进排序算法 (希尔排序,堆排序,归并排序,快速排序)
这边主要学习几个常用的算法,也是最近一舍友去面试时说,现在问的算法好多。
然后这礼拜断断续续的从周一到周四,抽了点时间温故而知新,顺便也保持做笔记的好习惯。(我这是有多闲啊!)
在最基本的排序算法中,快排是出境率最高的。也是这些算法中相对来说效率最优异的。
我顺便就再去看了遍这几个算法的实现。因为可能说你了解是了解,转化成代码时,还真有点难度。我就当复习复习
实现语言我用的是java,因为比较熟,但是其真正要写得优雅和简洁,那就得c来写。并且在目前大部分数据结构书上也都是C来实现教学的。
我这用java,权当走一遍思路流程。
一:简单排序
这里主要包括3种:
1.冒泡排序。操作思想是:不断两两比较和交换。
也是最简单的排序。
简单排序的思路很简单,依次比较相邻的两个数,将小数放在前面,大数放在后面。2层循环
内层循环一次后比较相邻的哪个大小,外层循环一次后,确定了末尾的元素为最大值。
因此下次内层训话后可以不用在比较最末尾的两元素的比较。
整体的比较次数即为:(1+n)*n/2 复杂度为O(n^2)。
基本实现Java代码:
[java] view plaincopy
private static int[] BubbleSort(int[] nums){
int count = 0;
for(int i = 0 ; i < nums.length-1; i++){
for(int j = 0; j < nums.length-i-1;j++){
count++;
if(nums[j] > nums [j+1]){
int temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
System.out.println("执行比较次数:"+count);
return nums;
}
冒泡的一点优化:
比如我有一个数组是部分有序的 {3,2,5,7,8,9}
那么比较外层i = 0的时候 内循环结束后其实整个序列就是排序完了。但是按上面的逻辑,外层循环又执行了i++,即i =1,在跳进内层循环比较。
一圈比较下来后其实根本没有发生元素交换,因为他本身已经是有序的了。然后紧接着i =2,3,4.。。。其实此时就完全可以退出整个循环了。
因此,我们增加一个标志位,对以上代码做一点点改进
[java] view plaincopy
private static int[] BubbleSort(int[] nums) {
int count = 0;
boolean flag = true;
for (int i = 0; i < nums.length - 1 &&flag ; i++) {//外层训话
flag = false;
for (int j = 0; j < nums.length - i - 1; j++) {//内层循环
count++;
if (nums[j] > nums[j + 1]) {//比较大小,大的放后面,小的放前面
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
flag = true;
}
}
}
System.out.println("执行比较次数:" + count);
return nums;
}
冒泡法的变种:鸡尾酒排序。基本的思路是,先从左端升序,再从右端降序。
[java] view plaincopy
private static int[] cockTail(int[] nums) {
int count = 0;
boolean flag = true;
int left = 0;
int right = nums.length-1;
while(flag){
flag = false;
for(int i = left; i<right;i++){
if (nums[i] > nums[i + 1]) {
int temp = nums[i];
nums[i] = nums[i + 1];
nums[i + 1] = temp;
flag = true;
}
count++;
}
right --;
for(int i = right; i>left;i--){
if (nums[i-1] > nums[i]) {
int temp = nums[i];
nums[i] = nums[i - 1];
nums[i - 1] = temp;
flag = true;
}
count++;
}
left ++;
}
System.out.println("执行比较次数:" + count);
return nums;
}
但是我测试了几次,鸡尾酒排序在查找的次数根本对传统的冒泡没有什么提升,但只是说因为随着left和right的缩小,元素在交换时移动的位置移动次数上可能会有一点减少。
而查了下资料还有一种是双向冒泡,基本实现和鸡尾酒这个很像。
总体来说冒泡排序就是最基本的一种排序方式。百度百科还表示有一种局部冒泡。但对于这样的一种排序,传统意义上的深入不如来的对新的排序研究来的有价值,当然,喜欢研究的朋友可以更深入的了解。我这边只是做下记录,以及自己学习的笔记。
2.简单选择排序
操作思想是在每一次扫描时选取关键字最小的记录作为最左端的元素。
[java] view plaincopy
private static void SimpleSelectSort(int[]nums){
for(int i = 0; i < nums.length; i++){//外层扫面控制
int min = i;//用来记录值最小的下标,默认假设第数组第一个元素为最小。
for(int j = i; j < nums.length ; j++){
if(nums[j] < nums[min]){//找出逼min下标中元素还小的值的下标
min = j;//保持min始终为最小元素的小标
}
}
if(i!=min){//一趟扫描结束后判断是否找出了最小的值,如果有的话就交换,将这个最小值移动到此次扫描数据的最前端
int temp = nums[i];
nums[i] = nums[min];
nums[min] = temp;
}
}
}
选择排序相对于了冒泡来说,在数据比较次数上其实没有不同,但是相对于减少了每次比较后若数据需要交换而带来的数据的移动操作,选择排序记录了要移动的下标,说白了,就是先记录下来最后做选择性的移动。总体来说可能比冒泡有一点的提升。
3.直接插入排序
[java] view plaincopy
private static void InsertSort(int[] nums) {
for (int i = 1; i < nums.length; i++) {// 外层对无序列表的扫描
if (nums[i] < nums[i - 1]) {
int temp = nums[i];// 保存该点的值,等会要将该值插入适当位置
int j = i - 1;
// while(j >= 0 && temp < nums[j]){
// nums[j + 1] = nums[j];
// j--;
// }
for (; j >= 0 && temp < nums[j]; j--) {// 往后移 tips此处千万不要 是nums[i] < nums[j]来比较,
//因为nums[i]这个值在一次移位后就被覆盖了,因此也为什么要用temp来保存这个值的原因
nums[j + 1] = nums[j];// 数组往后移
}
nums[j + 1] = temp;
}
}
}
整体来说,对于插入排序,数据的比较和交换的平均次数都是 n^2/2.
二:改进的算法
4.希尔排序.
排序思想:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。(百度百科)
希尔排序是插入排序的一种改进。
[java] view plaincopy
private static void shellSort(int[] nums){
int increment = nums.length;//增量
while(increment >1){
increment = increment/2 ;//增量计算
//一下基本同插入排序,只是直接插入排序我们比较时是增量是1,shell排序设置了一个自己的增量
for(int i = increment; i<nums.length;i++){
if(nums[i] < nums[i-increment]){
int temp = nums[i];
int j = i - increment;
for(;j >=0 && temp < nums[j];j-=increment ){
nums[j+increment] = nums[j];
}
nums[j+increment] = temp;
}
}
}
}
5.堆排序。
定义:“堆”定义
n个关键字序列Kl,K2,…,Kn称为(Heap),当且仅当该序列满足如下性质(简称为堆性质):
(1)ki<=k(2i)且ki<=k(2i+1)(1≤i≤ n),当然,这是小根堆,大根堆则换成>=号。//k(i)相当于二叉树的非叶结点,K(2i)则是左孩子,k(2i+1)是右孩子
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:
树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
思想:堆排序是选择排序的一种改进。选择排序的时,我们说是分为有序区和无序区(这边我们升序排,有序区在左边)。对数组排序扫描时第一遍
nums【0,n】所有的比较一边后选取最小的值放在坐标0这个位置,然后第二趟扫描 nums【1,n】,同样的选取最小值放在1位置。然后和我们可以知道,在第,二次对数组nums【1,n】扫描比较时,有很多比较其实在前面第一趟中已经做过,但是没有保存比较记录。因此选用树形的结构来保存。
堆排序的具体步骤:
第一步:将数组构造成堆(这边我们以大根堆来举例)
第二步:其实是第一步的深入,在构造大根堆时,我们根据二叉树特点可知我们可以从最后一个非叶子节点,即节点i = [n/2],开始扫描比较i节点和其子节点得到大小,如果子节点中大那个值比i节点大,则交换他们的位置。(tips注意点,此刻我们可能觉得i点和他的子节点对于大根堆的定义满足了,这边为了方便我们把这个算作一个事件。i节点事件后满足了大根堆定义。那么继续的i--。)然后操作到树的比较上面几层时(准确的说就是某个节点
j,处理完事件后,产生了节点交换,这时的他的一个子节点改变了,这个子节点非叶子节点,即,把他也拥有子节点,因为j节点的数据于其子节点child交换后,child节点和他的子节点的大根堆结构被破坏了。)看完括号里的注意事项,你应该知道某个节点 j在处理完节点事件后(即发生了数据交换)于j节点发生交换的子节点child拥有子节点(即 child * 2 +1>= n),则需要对child节点事件进行堆的重构。(感觉有点递归的意思了,而且本来树这结构就很容易让人想到递归这概念)。
第三步:第二步后,一棵大根堆就构造完了,此时根元素为最大值,将根元素和大根堆的最后一个元素交换。即,将最大值移动到有序区的最左端,带排序区的最右端。(数组的右端为有序)。
第四步:第三步结束后,则是类似于第二步的节点数据交换事件后的意思是差不多的,即,此刻原本根根节点的这个大根堆结构可能被破换了,那就是重构大根堆了(当然,此时构造大根堆的数组是nums【0,n-1】,而非nums【0,n-1】.。意思大家应该知道。
第五步:第四步结束后对于nums【0,n-1】构建完大堆树,重复第三部,将根元素和当前大根堆最后一个元素,即nums【n-1】互换,重复第四步。
n-1个循环后,排序结束。
时间复杂度分析:将待排序数组构造成大根堆的算法复杂级应该是在 nlogn(n/2个循环,循环里怎么里面是一个二叉树(这个怎么说呢?反正觉得有点二分的感觉。)抱歉我贫乏的专业词汇。假设我们把一个节点事件算法复杂度看成是一个O(1)级。那么最极端或是笼统的算,节点j在每一个节点事件操作后,都需要重构,再极端点的假设说操作的这个节点为根节点,那么要操作的时间级其实就是这颗树的深度 logn,当然这事最极端的想法,其实当节点为 j =【n/2】以及和这个节点在同一层的其他节点事件其实都是
O(1)),因此推测算法复杂级为 nlogn。(当然我这个不是专业的,只是个人的一点理解和认知)。
同理的可以理解后边的交换和重构算法级别还是在 nlogn,最后可得出为 n * logn。
实现代码;
[java] view plaincopy
private static void HeapSort(int[] nums){
int n = nums.length;
//step1:序列构建成大根堆
for(int i = (n-1)/2 ;i >= 0; i--){
//即对每个节点和其子节点的大根堆构造
HeapAdjust(nums, i, n);
}
//step2:遍历最大元素移动到末端
for(int i = n-1 ;i >0; i--){
int temp = nums[i];
nums[i] =nums[0];
nums[0] = temp;
//step3:重构
HeapAdjust(nums, 0, i);
}
}
/**
* 构建大根堆
* @param nums
* @param node
* @param length
*/
private static void HeapAdjust(int[] nums, int node, int length) {
if ((node*2+1) <=length-1) {// 保证该节点为非叶子节点,因为叶子节点就没意义了
int child = node * 2 + 1;//字节点坐标,主要是交换完后需要以该child为节点判断以及调整大根堆
if (child + 1 <= length-1) {//如果有有右子树
if (nums[child + 1] > nums[child]) {
child++;//判断后如果右子树大于左子树,child++,即等会要操作的是左子树节点
}
}
if(nums[node]< nums[child]){//大的子树与node比较
//交换
int temp = nums[node];
nums[node] =nums[child];
nums[child] = temp;
//再次重构
HeapAdjust(nums, child, length);
}
}
}
6.归并排序
概念:归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
思想:分治
归并算法是效率仅次于快排,并且稳定的排序。
在算法过程中需要申请附加的存储空间。
实现步骤:
首先我们要明白本身我们排序的是对于的是一个序列。对于要归并来说,首先要将该序列拆分成两个子序列,两个子序列各自排序成有序的,这就有又涉及到每个子序列的排序了,此刻我们若把一个子序列排序,不就又回到最前面的了么?这就是分治和递归的一种实现。
一:序列排序,先将序列分割成两个有序的子序列。然后执行归并算法
二:在一种将一个无需序列分割中两个子序列后,要执行归并,则要先对每个子序列进行排序,即,对方法一进行递归调用。
三:对于一个递归函数,则必须涉及到函数的结束,即当一个序列元素个数为1时,跳出递归
以下是归并算法的递归实现:
[java] view plaincopy
private static void MergingSort(int [] nums,int head,int tail){
int mid;
if(head >= tail)
return;
//while(head < tail){
//切分子序列,使之为有序子序列
mid = (tail + head)/2;
MergingSort(nums,head,mid);
MergingSort(nums, mid+1, tail);
//归并
Merging(nums, head, mid, tail);
//}
}
private static void Merging(int[] nums, int head, int mid, int tail) {
int[] temp = new int[tail-head+1];// 申请额外空间
int low = head;
int high = tail;
int j = mid + 1;
int p = 0;
//两个子序列都非空
while (head <= mid && j <= tail) {
if (nums[head] > nums[j]) {
temp[p++] = nums[j++];
} else {
temp[p++] = nums[head++];
}
}
//第一个子序列非空,将其中剩余的元素复制到temp中
while (head <= mid) {//
temp[p++] = nums[head++];
}
//第二个子序列非空,将其中剩余的元素复制到temp中
while (j <= tail) {//
temp[p++] = nums[j++];
}
//将缓存中的刷到归并序列中
for(int q=0, t =low ;t<=high;q++,t++){
nums[t]=temp[q];//归并完成后将结果复制回R[low..high]
} //Merge
}
注意点:上面我注释掉的while循环,这个真的是比较郁闷的,理论上来说这么while可行的,但是我测试后,发现跳不出while循环了,因为每次执行完
//归并
Merging(nums, head, mid, tail);
后while判断还是成立的,网上查了下资料,基本都也是这么写。可能因为代码我是按自己的思路书写的,诸侯将循环控制改成if来控制问题倒是解决了。
更多规范代码(比如C和c++)请参考规范文档。
以上是用递归实现的,下面以一个非递归实现的归并。其实思路是差不多的。
在上面我们是先思考将要排序序列分割成一个个子序列,然后再执行归并操作。然后整个形势刚好可以用递归实现,但是,递归来说,在代码的可读性和思路上能说比较好理解,但是递归的每次调用本身的创建副本,如果递归层数太深,内存资源是比较高的。
因此我们也可以转个思路,比如在一开始我们将该待排序序列分成每个子序列程度为1的多个子序列,然后将相邻的两个子序列执行归并排序。
[java] view plaincopy
private static void MergingSort2(int[] nums) {
int length = nums.length;
for (int n = 1; n < nums.length; n *= 2) {// 做logn 趟归并
int i;
for (i = 0; i + 2 * n - 1 <= length-1; i = i + 2 * n) {
Merging(nums, i, i + n - 1, i + 2 * n - 1);// 归并长度为length的两个相邻子文件
}
if (i + n - 1 < nums.length-1) // 尚有两个子文件,其中后一个长度小于length
Merging(nums, i, i + n - 1, nums.length-1); // 归并最后两个子文件
}
}
private static void Merging(int[] nums, int head, int mid, int tail) {
int[] temp = new int[tail-head+1];// 申请额外空间
int low = head;
int high = tail;
int j = mid + 1;
int p = 0;
//两个子序列都非空
while (head <= mid && j <= tail) {
if (nums[head] > nums[j]) {
temp[p++] = nums[j++];
} else {
temp[p++] = nums[head++];
}
}
//第一个子序列非空,将其中剩余的元素复制到temp中
while (head <= mid) {//
temp[p++] = nums[head++];
}
//第二个子序列非空,将其中剩余的元素复制到temp中
while (j <= tail) {//
temp[p++] = nums[j++];
}
//将缓存中的刷到归并序列中
for(int q=0, t =low ;t<=high;q++,t++){
nums[t]=temp[q];//归并完成后将结果复制回R[low..high]
} //Merge
}
上面在对logn趟循环中每趟对子序列执行两两归并其实有点混乱,可能说你在纸上画图时很简单,的确也很明了。
带式转成代码语言就比较恶心了。
可能有更好的代码格式的优化,大家可以自行设计
7.快速排序
快排是也算是冒泡的一种改进,同样的属于交换排序
基本思路是通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
整个来说是用到分治和递归的两种基本思想。
[java] view plaincopy
private static void quickSort(int[] nums, int low, int high) {
int mid;
if (low < high) {
mid = partition(nums, low, high);
quickSort(nums, low, mid - 1);
quickSort(nums, mid + 1, high);
}
}
private static int partition(int[] nums, int low, int high) {
int key = nums[low];// 设置
int temp;
while (low < high) {
while (low < high && nums[high] >= key)
high--;
if (low < high) {
temp = nums[low];
nums[low] = nums[high];
nums[high] = temp;
}
while (low < high && nums[low] <= key) {
low++;
}
if (low < high) {
temp = nums[low];
nums[low] = nums[high];
nums[high] = temp;
}
}
return low;
}
以上上快排最基本的实现。
对于快速排序的优化:第一点是中间值的选取:也就是这个key。
因为理论上来说,这个key选取的越接近中间数,那么对于分治后的左右两边越平衡,理解成树形式可以知道此刻树的深度越小,那递归层数也就越小了。
于是优化时就在对这个key取值上进行优化。现在一般就是取左端,中间,右端三个数后比较取一个处于三个数的中间的值作为最右端(因为我们函数取key值是nums[low],即最左端的值)。此时只需将微微改动
[java] view plaincopy
private static int partition(int[] nums, int low, int high) {
int middle = low+(high-low)/2;//中间元素的下标
int temp;
if(nums[low] > nums[high]){
temp = nums[low];
nums[low] = nums[high];
nums[high] = temp;
}
if(nums[middle] > nums[high]){
temp = nums[middle];
nums[middle] = nums[high];
nums[high] = temp;
}
//以上两个if后保证最小值和中间值处于middle和low位置,下面再用一个if来保证将中间值放在low位置
if(nums[middle] > nums[low]){
temp = nums[middle];
nums[middle] = nums[low];
nums[low] = temp;
}
int key = nums[low];// 设置
while (low < high) {
while (low < high && nums[high] >= key)
high--;
if (low < high) {
temp = nums[low];
nums[low] = nums[high];
nums[high] = temp;
}
while (low < high && nums[low] <= key) {
low++;
}
if (low < high) {
temp = nums[low];
nums[low] = nums[high];
nums[high] = temp;
}
}
return low;
}
其实可以把交换那个三句的代码写个单独方法。。。我这边就随意点了。
第二点:减少交换次数。
相对来说,快排是也是属于交换排序,在一趟扫描中(即low往high靠近)时,将交换改成替换
[java] view plaincopy
private static int partition(int[] nums, int low, int high) {
int middle = low+(high-low)/2;//中间元素的下标
int temp;
if(nums[low] > nums[high]){
temp = nums[low];
nums[low] = nums[high];
nums[high] = temp;
}
if(nums[middle] > nums[high]){
temp = nums[middle];
nums[middle] = nums[high];
nums[high] = temp;
}
//以上两个if后保证最小值和中间值处于middle和low位置,下面再用一个if来保证将中间值放在low位置
if(nums[middle] > nums[low]){
temp = nums[middle];
nums[middle] = nums[low];
nums[low] = temp;
}
int key = nums[low];// 设置
while (low < high) {
while (low < high && nums[high] >= key)
high--;
if (low < high) {
nums[low] = nums[high];
// temp = nums[low];
// nums[low] = nums[high];
// nums[high] = temp;
}
while (low < high && nums[low] <= key) {
low++;
}
if (low < high) {
nums[high] = nums[low];
// temp = nums[low];
// nums[low] = nums[high];
// nums[high] = temp;
}
}
nums[low] = key;
return low;
}
这个具体怎么理解,可以画下图就觉得,的确是这么着的。
最后再提到一点改进是用尾递归,实现代码:
[java] view plaincopy
private static void quickSort2(int[] nums, int low, int high) {
int mid;
while(low < high){
mid = partition(nums, low, high);
quickSort2(nums, low, mid - 1);
low = mid +1;
}
// if (low < high) {
// mid = partition(nums, low, high);
// quickSort2(nums, low, mid - 1);
// quickSort2(nums, mid + 1, high);
// }
}
十三个经典算法研究与总结、目录+索引
http://blog.csdn.net/v_july_v/article/details/6305212
排序的一些概念
稳定性和不稳定性:关键字相等的记录在排序情况不唯一。
内排序和外排序:简单来说前者的操作都是在内存中,后者数据太多,存在于外部存储设备的交互操作。
一般我们说的的算法都是值指的内排序。
对于排序的分类可能有好几种:
一般按操作方式和思想可分为:交换,插入,选择,合并等。
也有按计算复杂度的来分的,O(n^2)简单排序(冒泡,简单选折,直接插入)和改进排序算法 (希尔排序,堆排序,归并排序,快速排序)
这边主要学习几个常用的算法,也是最近一舍友去面试时说,现在问的算法好多。
然后这礼拜断断续续的从周一到周四,抽了点时间温故而知新,顺便也保持做笔记的好习惯。(我这是有多闲啊!)
在最基本的排序算法中,快排是出境率最高的。也是这些算法中相对来说效率最优异的。
我顺便就再去看了遍这几个算法的实现。因为可能说你了解是了解,转化成代码时,还真有点难度。我就当复习复习
实现语言我用的是java,因为比较熟,但是其真正要写得优雅和简洁,那就得c来写。并且在目前大部分数据结构书上也都是C来实现教学的。
我这用java,权当走一遍思路流程。
一:简单排序
这里主要包括3种:
1.冒泡排序。操作思想是:不断两两比较和交换。
也是最简单的排序。
简单排序的思路很简单,依次比较相邻的两个数,将小数放在前面,大数放在后面。2层循环
内层循环一次后比较相邻的哪个大小,外层循环一次后,确定了末尾的元素为最大值。
因此下次内层训话后可以不用在比较最末尾的两元素的比较。
整体的比较次数即为:(1+n)*n/2 复杂度为O(n^2)。
基本实现Java代码:
[java] view plaincopy
private static int[] BubbleSort(int[] nums){
int count = 0;
for(int i = 0 ; i < nums.length-1; i++){
for(int j = 0; j < nums.length-i-1;j++){
count++;
if(nums[j] > nums [j+1]){
int temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
System.out.println("执行比较次数:"+count);
return nums;
}
冒泡的一点优化:
比如我有一个数组是部分有序的 {3,2,5,7,8,9}
那么比较外层i = 0的时候 内循环结束后其实整个序列就是排序完了。但是按上面的逻辑,外层循环又执行了i++,即i =1,在跳进内层循环比较。
一圈比较下来后其实根本没有发生元素交换,因为他本身已经是有序的了。然后紧接着i =2,3,4.。。。其实此时就完全可以退出整个循环了。
因此,我们增加一个标志位,对以上代码做一点点改进
[java] view plaincopy
private static int[] BubbleSort(int[] nums) {
int count = 0;
boolean flag = true;
for (int i = 0; i < nums.length - 1 &&flag ; i++) {//外层训话
flag = false;
for (int j = 0; j < nums.length - i - 1; j++) {//内层循环
count++;
if (nums[j] > nums[j + 1]) {//比较大小,大的放后面,小的放前面
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
flag = true;
}
}
}
System.out.println("执行比较次数:" + count);
return nums;
}
冒泡法的变种:鸡尾酒排序。基本的思路是,先从左端升序,再从右端降序。
[java] view plaincopy
private static int[] cockTail(int[] nums) {
int count = 0;
boolean flag = true;
int left = 0;
int right = nums.length-1;
while(flag){
flag = false;
for(int i = left; i<right;i++){
if (nums[i] > nums[i + 1]) {
int temp = nums[i];
nums[i] = nums[i + 1];
nums[i + 1] = temp;
flag = true;
}
count++;
}
right --;
for(int i = right; i>left;i--){
if (nums[i-1] > nums[i]) {
int temp = nums[i];
nums[i] = nums[i - 1];
nums[i - 1] = temp;
flag = true;
}
count++;
}
left ++;
}
System.out.println("执行比较次数:" + count);
return nums;
}
但是我测试了几次,鸡尾酒排序在查找的次数根本对传统的冒泡没有什么提升,但只是说因为随着left和right的缩小,元素在交换时移动的位置移动次数上可能会有一点减少。
而查了下资料还有一种是双向冒泡,基本实现和鸡尾酒这个很像。
总体来说冒泡排序就是最基本的一种排序方式。百度百科还表示有一种局部冒泡。但对于这样的一种排序,传统意义上的深入不如来的对新的排序研究来的有价值,当然,喜欢研究的朋友可以更深入的了解。我这边只是做下记录,以及自己学习的笔记。
2.简单选择排序
操作思想是在每一次扫描时选取关键字最小的记录作为最左端的元素。
[java] view plaincopy
private static void SimpleSelectSort(int[]nums){
for(int i = 0; i < nums.length; i++){//外层扫面控制
int min = i;//用来记录值最小的下标,默认假设第数组第一个元素为最小。
for(int j = i; j < nums.length ; j++){
if(nums[j] < nums[min]){//找出逼min下标中元素还小的值的下标
min = j;//保持min始终为最小元素的小标
}
}
if(i!=min){//一趟扫描结束后判断是否找出了最小的值,如果有的话就交换,将这个最小值移动到此次扫描数据的最前端
int temp = nums[i];
nums[i] = nums[min];
nums[min] = temp;
}
}
}
选择排序相对于了冒泡来说,在数据比较次数上其实没有不同,但是相对于减少了每次比较后若数据需要交换而带来的数据的移动操作,选择排序记录了要移动的下标,说白了,就是先记录下来最后做选择性的移动。总体来说可能比冒泡有一点的提升。
3.直接插入排序
[java] view plaincopy
private static void InsertSort(int[] nums) {
for (int i = 1; i < nums.length; i++) {// 外层对无序列表的扫描
if (nums[i] < nums[i - 1]) {
int temp = nums[i];// 保存该点的值,等会要将该值插入适当位置
int j = i - 1;
// while(j >= 0 && temp < nums[j]){
// nums[j + 1] = nums[j];
// j--;
// }
for (; j >= 0 && temp < nums[j]; j--) {// 往后移 tips此处千万不要 是nums[i] < nums[j]来比较,
//因为nums[i]这个值在一次移位后就被覆盖了,因此也为什么要用temp来保存这个值的原因
nums[j + 1] = nums[j];// 数组往后移
}
nums[j + 1] = temp;
}
}
}
整体来说,对于插入排序,数据的比较和交换的平均次数都是 n^2/2.
二:改进的算法
4.希尔排序.
排序思想:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。(百度百科)
希尔排序是插入排序的一种改进。
[java] view plaincopy
private static void shellSort(int[] nums){
int increment = nums.length;//增量
while(increment >1){
increment = increment/2 ;//增量计算
//一下基本同插入排序,只是直接插入排序我们比较时是增量是1,shell排序设置了一个自己的增量
for(int i = increment; i<nums.length;i++){
if(nums[i] < nums[i-increment]){
int temp = nums[i];
int j = i - increment;
for(;j >=0 && temp < nums[j];j-=increment ){
nums[j+increment] = nums[j];
}
nums[j+increment] = temp;
}
}
}
}
5.堆排序。
定义:“堆”定义
n个关键字序列Kl,K2,…,Kn称为(Heap),当且仅当该序列满足如下性质(简称为堆性质):
(1)ki<=k(2i)且ki<=k(2i+1)(1≤i≤ n),当然,这是小根堆,大根堆则换成>=号。//k(i)相当于二叉树的非叶结点,K(2i)则是左孩子,k(2i+1)是右孩子
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:
树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
思想:堆排序是选择排序的一种改进。选择排序的时,我们说是分为有序区和无序区(这边我们升序排,有序区在左边)。对数组排序扫描时第一遍
nums【0,n】所有的比较一边后选取最小的值放在坐标0这个位置,然后第二趟扫描 nums【1,n】,同样的选取最小值放在1位置。然后和我们可以知道,在第,二次对数组nums【1,n】扫描比较时,有很多比较其实在前面第一趟中已经做过,但是没有保存比较记录。因此选用树形的结构来保存。
堆排序的具体步骤:
第一步:将数组构造成堆(这边我们以大根堆来举例)
第二步:其实是第一步的深入,在构造大根堆时,我们根据二叉树特点可知我们可以从最后一个非叶子节点,即节点i = [n/2],开始扫描比较i节点和其子节点得到大小,如果子节点中大那个值比i节点大,则交换他们的位置。(tips注意点,此刻我们可能觉得i点和他的子节点对于大根堆的定义满足了,这边为了方便我们把这个算作一个事件。i节点事件后满足了大根堆定义。那么继续的i--。)然后操作到树的比较上面几层时(准确的说就是某个节点
j,处理完事件后,产生了节点交换,这时的他的一个子节点改变了,这个子节点非叶子节点,即,把他也拥有子节点,因为j节点的数据于其子节点child交换后,child节点和他的子节点的大根堆结构被破坏了。)看完括号里的注意事项,你应该知道某个节点 j在处理完节点事件后(即发生了数据交换)于j节点发生交换的子节点child拥有子节点(即 child * 2 +1>= n),则需要对child节点事件进行堆的重构。(感觉有点递归的意思了,而且本来树这结构就很容易让人想到递归这概念)。
第三步:第二步后,一棵大根堆就构造完了,此时根元素为最大值,将根元素和大根堆的最后一个元素交换。即,将最大值移动到有序区的最左端,带排序区的最右端。(数组的右端为有序)。
第四步:第三步结束后,则是类似于第二步的节点数据交换事件后的意思是差不多的,即,此刻原本根根节点的这个大根堆结构可能被破换了,那就是重构大根堆了(当然,此时构造大根堆的数组是nums【0,n-1】,而非nums【0,n-1】.。意思大家应该知道。
第五步:第四步结束后对于nums【0,n-1】构建完大堆树,重复第三部,将根元素和当前大根堆最后一个元素,即nums【n-1】互换,重复第四步。
n-1个循环后,排序结束。
时间复杂度分析:将待排序数组构造成大根堆的算法复杂级应该是在 nlogn(n/2个循环,循环里怎么里面是一个二叉树(这个怎么说呢?反正觉得有点二分的感觉。)抱歉我贫乏的专业词汇。假设我们把一个节点事件算法复杂度看成是一个O(1)级。那么最极端或是笼统的算,节点j在每一个节点事件操作后,都需要重构,再极端点的假设说操作的这个节点为根节点,那么要操作的时间级其实就是这颗树的深度 logn,当然这事最极端的想法,其实当节点为 j =【n/2】以及和这个节点在同一层的其他节点事件其实都是
O(1)),因此推测算法复杂级为 nlogn。(当然我这个不是专业的,只是个人的一点理解和认知)。
同理的可以理解后边的交换和重构算法级别还是在 nlogn,最后可得出为 n * logn。
实现代码;
[java] view plaincopy
private static void HeapSort(int[] nums){
int n = nums.length;
//step1:序列构建成大根堆
for(int i = (n-1)/2 ;i >= 0; i--){
//即对每个节点和其子节点的大根堆构造
HeapAdjust(nums, i, n);
}
//step2:遍历最大元素移动到末端
for(int i = n-1 ;i >0; i--){
int temp = nums[i];
nums[i] =nums[0];
nums[0] = temp;
//step3:重构
HeapAdjust(nums, 0, i);
}
}
/**
* 构建大根堆
* @param nums
* @param node
* @param length
*/
private static void HeapAdjust(int[] nums, int node, int length) {
if ((node*2+1) <=length-1) {// 保证该节点为非叶子节点,因为叶子节点就没意义了
int child = node * 2 + 1;//字节点坐标,主要是交换完后需要以该child为节点判断以及调整大根堆
if (child + 1 <= length-1) {//如果有有右子树
if (nums[child + 1] > nums[child]) {
child++;//判断后如果右子树大于左子树,child++,即等会要操作的是左子树节点
}
}
if(nums[node]< nums[child]){//大的子树与node比较
//交换
int temp = nums[node];
nums[node] =nums[child];
nums[child] = temp;
//再次重构
HeapAdjust(nums, child, length);
}
}
}
6.归并排序
概念:归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
思想:分治
归并算法是效率仅次于快排,并且稳定的排序。
在算法过程中需要申请附加的存储空间。
实现步骤:
首先我们要明白本身我们排序的是对于的是一个序列。对于要归并来说,首先要将该序列拆分成两个子序列,两个子序列各自排序成有序的,这就有又涉及到每个子序列的排序了,此刻我们若把一个子序列排序,不就又回到最前面的了么?这就是分治和递归的一种实现。
一:序列排序,先将序列分割成两个有序的子序列。然后执行归并算法
二:在一种将一个无需序列分割中两个子序列后,要执行归并,则要先对每个子序列进行排序,即,对方法一进行递归调用。
三:对于一个递归函数,则必须涉及到函数的结束,即当一个序列元素个数为1时,跳出递归
以下是归并算法的递归实现:
[java] view plaincopy
private static void MergingSort(int [] nums,int head,int tail){
int mid;
if(head >= tail)
return;
//while(head < tail){
//切分子序列,使之为有序子序列
mid = (tail + head)/2;
MergingSort(nums,head,mid);
MergingSort(nums, mid+1, tail);
//归并
Merging(nums, head, mid, tail);
//}
}
private static void Merging(int[] nums, int head, int mid, int tail) {
int[] temp = new int[tail-head+1];// 申请额外空间
int low = head;
int high = tail;
int j = mid + 1;
int p = 0;
//两个子序列都非空
while (head <= mid && j <= tail) {
if (nums[head] > nums[j]) {
temp[p++] = nums[j++];
} else {
temp[p++] = nums[head++];
}
}
//第一个子序列非空,将其中剩余的元素复制到temp中
while (head <= mid) {//
temp[p++] = nums[head++];
}
//第二个子序列非空,将其中剩余的元素复制到temp中
while (j <= tail) {//
temp[p++] = nums[j++];
}
//将缓存中的刷到归并序列中
for(int q=0, t =low ;t<=high;q++,t++){
nums[t]=temp[q];//归并完成后将结果复制回R[low..high]
} //Merge
}
注意点:上面我注释掉的while循环,这个真的是比较郁闷的,理论上来说这么while可行的,但是我测试后,发现跳不出while循环了,因为每次执行完
//归并
Merging(nums, head, mid, tail);
后while判断还是成立的,网上查了下资料,基本都也是这么写。可能因为代码我是按自己的思路书写的,诸侯将循环控制改成if来控制问题倒是解决了。
更多规范代码(比如C和c++)请参考规范文档。
以上是用递归实现的,下面以一个非递归实现的归并。其实思路是差不多的。
在上面我们是先思考将要排序序列分割成一个个子序列,然后再执行归并操作。然后整个形势刚好可以用递归实现,但是,递归来说,在代码的可读性和思路上能说比较好理解,但是递归的每次调用本身的创建副本,如果递归层数太深,内存资源是比较高的。
因此我们也可以转个思路,比如在一开始我们将该待排序序列分成每个子序列程度为1的多个子序列,然后将相邻的两个子序列执行归并排序。
[java] view plaincopy
private static void MergingSort2(int[] nums) {
int length = nums.length;
for (int n = 1; n < nums.length; n *= 2) {// 做logn 趟归并
int i;
for (i = 0; i + 2 * n - 1 <= length-1; i = i + 2 * n) {
Merging(nums, i, i + n - 1, i + 2 * n - 1);// 归并长度为length的两个相邻子文件
}
if (i + n - 1 < nums.length-1) // 尚有两个子文件,其中后一个长度小于length
Merging(nums, i, i + n - 1, nums.length-1); // 归并最后两个子文件
}
}
private static void Merging(int[] nums, int head, int mid, int tail) {
int[] temp = new int[tail-head+1];// 申请额外空间
int low = head;
int high = tail;
int j = mid + 1;
int p = 0;
//两个子序列都非空
while (head <= mid && j <= tail) {
if (nums[head] > nums[j]) {
temp[p++] = nums[j++];
} else {
temp[p++] = nums[head++];
}
}
//第一个子序列非空,将其中剩余的元素复制到temp中
while (head <= mid) {//
temp[p++] = nums[head++];
}
//第二个子序列非空,将其中剩余的元素复制到temp中
while (j <= tail) {//
temp[p++] = nums[j++];
}
//将缓存中的刷到归并序列中
for(int q=0, t =low ;t<=high;q++,t++){
nums[t]=temp[q];//归并完成后将结果复制回R[low..high]
} //Merge
}
上面在对logn趟循环中每趟对子序列执行两两归并其实有点混乱,可能说你在纸上画图时很简单,的确也很明了。
带式转成代码语言就比较恶心了。
可能有更好的代码格式的优化,大家可以自行设计
7.快速排序
快排是也算是冒泡的一种改进,同样的属于交换排序
基本思路是通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
整个来说是用到分治和递归的两种基本思想。
[java] view plaincopy
private static void quickSort(int[] nums, int low, int high) {
int mid;
if (low < high) {
mid = partition(nums, low, high);
quickSort(nums, low, mid - 1);
quickSort(nums, mid + 1, high);
}
}
private static int partition(int[] nums, int low, int high) {
int key = nums[low];// 设置
int temp;
while (low < high) {
while (low < high && nums[high] >= key)
high--;
if (low < high) {
temp = nums[low];
nums[low] = nums[high];
nums[high] = temp;
}
while (low < high && nums[low] <= key) {
low++;
}
if (low < high) {
temp = nums[low];
nums[low] = nums[high];
nums[high] = temp;
}
}
return low;
}
以上上快排最基本的实现。
对于快速排序的优化:第一点是中间值的选取:也就是这个key。
因为理论上来说,这个key选取的越接近中间数,那么对于分治后的左右两边越平衡,理解成树形式可以知道此刻树的深度越小,那递归层数也就越小了。
于是优化时就在对这个key取值上进行优化。现在一般就是取左端,中间,右端三个数后比较取一个处于三个数的中间的值作为最右端(因为我们函数取key值是nums[low],即最左端的值)。此时只需将微微改动
[java] view plaincopy
private static int partition(int[] nums, int low, int high) {
int middle = low+(high-low)/2;//中间元素的下标
int temp;
if(nums[low] > nums[high]){
temp = nums[low];
nums[low] = nums[high];
nums[high] = temp;
}
if(nums[middle] > nums[high]){
temp = nums[middle];
nums[middle] = nums[high];
nums[high] = temp;
}
//以上两个if后保证最小值和中间值处于middle和low位置,下面再用一个if来保证将中间值放在low位置
if(nums[middle] > nums[low]){
temp = nums[middle];
nums[middle] = nums[low];
nums[low] = temp;
}
int key = nums[low];// 设置
while (low < high) {
while (low < high && nums[high] >= key)
high--;
if (low < high) {
temp = nums[low];
nums[low] = nums[high];
nums[high] = temp;
}
while (low < high && nums[low] <= key) {
low++;
}
if (low < high) {
temp = nums[low];
nums[low] = nums[high];
nums[high] = temp;
}
}
return low;
}
其实可以把交换那个三句的代码写个单独方法。。。我这边就随意点了。
第二点:减少交换次数。
相对来说,快排是也是属于交换排序,在一趟扫描中(即low往high靠近)时,将交换改成替换
[java] view plaincopy
private static int partition(int[] nums, int low, int high) {
int middle = low+(high-low)/2;//中间元素的下标
int temp;
if(nums[low] > nums[high]){
temp = nums[low];
nums[low] = nums[high];
nums[high] = temp;
}
if(nums[middle] > nums[high]){
temp = nums[middle];
nums[middle] = nums[high];
nums[high] = temp;
}
//以上两个if后保证最小值和中间值处于middle和low位置,下面再用一个if来保证将中间值放在low位置
if(nums[middle] > nums[low]){
temp = nums[middle];
nums[middle] = nums[low];
nums[low] = temp;
}
int key = nums[low];// 设置
while (low < high) {
while (low < high && nums[high] >= key)
high--;
if (low < high) {
nums[low] = nums[high];
// temp = nums[low];
// nums[low] = nums[high];
// nums[high] = temp;
}
while (low < high && nums[low] <= key) {
low++;
}
if (low < high) {
nums[high] = nums[low];
// temp = nums[low];
// nums[low] = nums[high];
// nums[high] = temp;
}
}
nums[low] = key;
return low;
}
这个具体怎么理解,可以画下图就觉得,的确是这么着的。
最后再提到一点改进是用尾递归,实现代码:
[java] view plaincopy
private static void quickSort2(int[] nums, int low, int high) {
int mid;
while(low < high){
mid = partition(nums, low, high);
quickSort2(nums, low, mid - 1);
low = mid +1;
}
// if (low < high) {
// mid = partition(nums, low, high);
// quickSort2(nums, low, mid - 1);
// quickSort2(nums, mid + 1, high);
// }
}
发表评论
-
java的8种排序
2013-03-19 22:51 954url:http://www.iteye.com/topic ... -
排序算法分析之冒泡排序
2012-05-25 11:27 1533冒泡排序(Bubble Sort)是一种简单的排序算法。它重复 ... -
想对集合说的一些话
2012-04-24 00:11 1005Java的集合很有用,自己看过很多了,但是总是感觉很模糊,用起 ... -
数据结构(c语言)
2012-04-19 21:29 11361. 经典算法 单链表:遍 ... -
java中数据结构二分查法
2012-04-20 00:19 1321数据结构和算法是一个程序的灵魂,优化程序的主要手段。在查询里, ... -
插入排序
2012-04-21 21:16 944插入排序无非就是在原来已经排好序的基础上再一个个添加元素,每次 ... -
java经典算法40题
2012-04-14 12:16 1698排序算法:http://www.cnblogs.com/mor ... -
数据结构与算法基础
2012-03-29 09:31 12161.arraylist(底层数组实现) ... -
2012/3/27----归并排序
2012-03-27 13:58 1002通过使用分治算法的思想来对数组进行排序(这里叫做归并排序),分 ... -
排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序
2012-03-18 18:06 1451先推荐一篇关于排序算法的文章:http://www.cppbl ... -
深入arraylist,linkedlist,hashmap,hashset源码(2012/3/18)
2012-03-18 16:30 15511.冒泡排序 2.arraylist存 ... -
快速排序算法原理与实现/交换排序
2012-03-19 09:45 1513快速排序的大致思想为取到中间位置的元素,其他元素和其一一比较, ...
相关推荐
本书《更多Windows白话经典算法之七大排序第2版》是一部深入浅出讲解七种经典排序算法的著作,旨在帮助读者理解并掌握冒泡排序、直接插入排序、直接选择排序、希尔排序、归并排序、快速排序以及堆排序等基本概念和...
本压缩包"常见的七大排序算法Java实现.zip"包含了七种经典的排序算法在Java语言中的实现。尽管文件列表中并未明确列出每种排序算法的名称,但根据常规,这七大排序算法可能包括冒泡排序、插入排序、选择排序、快速...
《白话经典算法之七大排序》是一本专为初学者设计的算法教程,旨在通过简单易懂的语言,帮助读者深入浅出地理解并掌握七大排序算法。这些排序算法是计算机科学与信息技术领域的基础,对于提升编程能力和解决实际问题...
### 白话经典算法之七大排序 #### 一、冒泡排序 冒泡排序是一种简单直观的排序算法,它的基本思想是从第一个元素开始,比较相邻元素的大小,如果前一个元素大于后一个元素则交换它们的位置,这样一轮比较下来,...
希尔排序是基于插入排序的算法,通过将原来的一组记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的记录越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。 ...
《MoreWindows白话经典算法之七大排序》是针对计算机编程中的一个重要主题——排序算法的一份详细解析。排序算法是计算机科学的基础,对于任何处理数据的软件系统来说,无论是数据分析、数据库管理还是图形用户界面...
### 经典七大排序算法详解 #### 一、冒泡排序 冒泡排序是一种简单的排序算法,通过重复地遍历列表,比较每对相邻元素,若顺序错误则交换它们。遍历列表的工作会重复进行直到没有更多的交换需要,也就是说列表已经...
在本资源"经典算法之七大排序.zip_organized6k4_排序_排序算法"中,包含了七种经典的排序算法,它们分别是:冒泡排序、直接插入排序、直接选择排序、希尔排序、归并排序、快速排序和堆排序。以下将对这七种排序算法...
在编程领域,排序算法是数据结构与算法学习中的基础部分,尤其在Java中,掌握不同的排序算法对于优化程序性能至关重要。本资源包含了七种经典的排序算法实现,它们分别是冒泡排序、插入排序、递归排序(这里可能是指...
本文将深入探讨七大常用排序算法,并结合C#语言的实现进行讲解。 一、冒泡排序(Bubble Sort) 冒泡排序是一种简单的排序算法,通过重复遍历待排序的数列,依次比较相邻元素并交换位置,直到没有任何一对数字需要...
这里我们将深入探讨七种常见的VB排序算法及其在VB6中的实现方式。 1. **冒泡排序(Bubble Sort)** 冒泡排序是最基础的排序算法之一,通过不断交换相邻的逆序元素来逐步排序数组。在VB6中,你可以创建一个For......
这个"七种常见的VB排序算法示例程序.rar"压缩包包含了一系列的VB代码示例,涵盖了从初级到高级的不同排序算法。让我们逐一探讨这些算法的原理、实现方式以及它们在实际应用中的优缺点。 1. 起泡排序(Bubble Sort)...
本资源"MoreWindows白话经典算法之七大排序(高清版).pdf"提供了一套详尽的排序算法讲解,涵盖了七大经典的排序算法。以下是这些排序算法的详细介绍: 1. 冒泡排序(Bubble Sort): 冒泡排序是一种简单的交换排序,...
算法系列15天速成第一天,主题为“七大经典排序【上】”,介绍了四种排序分类中的前两类:交换排序和选择排序。 交换排序中包括了冒泡排序和快速排序。冒泡排序是一种简单的排序算法,它重复地遍历要排序的数列,一...
### Java常用的七大排序算法 #### 1. 插入排序算法 插入排序是一种简单直观的排序算法。它的基本思想是:对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。 - **算法步骤**: 1. 将第一待排序...
冒泡排序是最基础的排序算法之一,通过不断交换相邻的逆序元素来逐步排序。它的时间复杂度在最坏情况下为O(n²),在最好情况下为O(n)。 2. **选择排序(Selection Sort)** 选择排序每次找出未排序部分的最小(或...
在编程领域,排序算法是计算机科学中的核心概念,它们用于组织和优化数据处理。C语言是一种广泛应用的编程...通过学习这些C语言实现,可以帮助开发者深入理解排序算法的工作原理,从而在实际问题中选择合适的排序方法。
在计算机科学领域,排序算法是数据结构与算法中不可或缺的一部分,它们用于将一组无序的数据按照特定顺序排列。本文将详细介绍七种基本排序算法,包括插入排序、快速排序、希尔排序、归并排序、选择排序、冒泡排序...
描述中的“七种排序算法动态演示软件”是一个用于教育和学习的工具,用户可以手动输入数据,观察每种排序算法的执行过程,这有助于理解各种排序算法的内部机制和性能特点。软件基于WPF(Windows Presentation ...
快速排序是一种高效的排序算法,采用分治法策略,它的时间复杂度平均为O(nlogn),最坏情况为O(n^2)。快速排序的基本步骤包括: 1. 选择一个基准元素(pivot),通常选择序列中的第一个元素或最后一个元素。 2. 重新...