- 浏览: 908661 次
- 性别:
- 来自: 武汉
-
文章分类
最新评论
-
小宇宙_WZY:
膜拜一下大神,解决了我一个大问题,非常感谢 orz
【解惑】深入jar包:从jar包中读取资源文件 -
JKL852qaz:
感谢,遇到相同的问题!
【解惑】深入jar包:从jar包中读取资源文件 -
lgh1992314:
为什么java中调用final方法是用invokevirtua ...
【解惑】Java动态绑定机制的内幕 -
鲁曼1991:
说的都有道理,protected只能被同一级包的类所调用
【解惑】真正理解了protected的作用范围 -
鲁曼1991:
...
【总结】String in Java
(1) 简单选择排序 O(N^2)
一趟简单选择排序的操作为:通过n-i 次关键字间的比较,从n-i+1 个记录中选择出关键字最小的记录,并和第 i (i<=i<=n)个记录交换之。
#include<iostream.h>
/***************************************
* 简单选择排序 Simple Selection Sort *
***************************************/
class SimpleSelectSort{
public:
//递增排序
static void inc_sort(int keys[],int size);
};
void SimpleSelectSort :: inc_sort(int keys[], int size){
for(int i=0;i<size;i++){
int min_key=keys[i]; //存储每一趟排序的最小值
int min_key_pos=i; //存储最小值的位置
for(int j=i+1;j<size;j++){
if(min_key>keys[j]){ //定位最小值
min_key=keys[j];
min_key_pos=j;
}
}
keys[min_key_pos]=keys[i]; //将选择的最小值交换位置
keys[i]=min_key;
}
for(int k=0;k<size;k++)
cout<<keys[k]<<" ";
cout<<endl;
}
//Test SimpleSelectSort
void main(){
int raw[]={49,38,65,97,76,13,27,49};
int size=sizeof(raw)/sizeof(int);
SimpleSelectSort::inc_sort(raw,size);
}
简单选择排序的时间复杂度为O(N^2),空间复杂度为O(1),排序方法是稳定的 。这种排序方法在n个关键字中选出最小值,至少进行n-1次比较,然而,继续在剩余的n-1个关键字中选择次小值就并非一定要进行n-2次比较了。下面的树形选择排序后一轮比较可以利用前一轮的比较结果,从而大大减少比较的次数。
(2) 树形选择排序 O(N * logN)
树形选择排序(Tree Selection Sort),又称竞标赛排序(Tournament Sort),是一种按照竞标赛思想进行的选择排序方法。首先对n个记录的关键字两两比较,然后在其中[n/2]个较小者之间在进行两两比较,如此重复,直至选出最小关键字的记录为止。这个过程可用一颗有n个叶子结点的完全二叉树表示。 下图展示了树形选择排序的过程:

(a)图选择出最小值13需要7次比较,但是(b)图选择第二小的27就只需要3次了。应为(a)图中的最小值13已经找到,只需要在(b)图中将13的位置赋值为无穷大,这样,就只需要再次比较树的一部分就可以找到第二小的值。
#include<iostream.h>
#include<malloc.h>
#define MAX_INT 32767;
typedef struct sort_node{
int key; //待排关键字
int pos; //此关键字在待排序列中的位置
}SortNode;
int level=1;
SortNode **level_point;
//记录每一层的关键字容量的连续空间
int *level_count;
//记录已经排序号的关键字序列
int *sorted_keys;
//释放多维指针
void freeAll(SortNode ** deleted, int size){
for(int i=0;i<size;i++)
free(deleted[i]);
}
//递增排序
void inc_sort(int keys[],int size){
//开辟存储排序序列的容量
sorted_keys=(int *)malloc(size*sizeof(int));
//根据待排序列的数量确定排序树的层次
int a_size=size;
bool isPower=true;
if(a_size>1){
while(a_size!=1){
if(a_size%2==1)
isPower=false;
level++;
a_size/=2;
}
}
if(isPower==false) level++;
//够着排序树的内存结构,为每一层开辟可以容纳一定数量关键字的内存空间
level_point=(SortNode **)malloc(level*sizeof(SortNode *));
level_count=(int *)malloc(level*sizeof(int));
int level_size=size;
for(int l=0;l<level;l++){
level_count[l]=level_size;
level_point[l]=(SortNode *)malloc(level_size*sizeof(SortNode));
level_size=level_size/2+level_size%2;
}
//为第0层赋值待排序列,并建立排序树,找到第一次最小的关键字
for(int i=0;i<size;i++){
level_point[0][i].key=keys[i];
level_point[0][i].pos=i;
}
int cur_level=1;
while(cur_level<level){
for(int j=0;j<level_count[cur_level];j++){
int left_child=level_point[cur_level-1][j*2].key;
//没有右孩子
if((j*2+1)>=level_count[cur_level-1]){
level_point[cur_level][j].key=left_child;
level_point[cur_level][j].pos=level_point[cur_level-1][j*2].pos;
}else{
int right_child=level_point[cur_level-1][j*2+1].key;
level_point[cur_level][j].key=left_child<=right_child ? left_child : right_child;
level_point[cur_level][j].pos=left_child<=right_child ? level_point[cur_level-1][j*2].pos : level_point[cur_level-1][j*2+1].pos;
}
}
cur_level++;
}
//打印第一次的树形选择排序:
cout<<"第1次树形选择排序 (关键字 - 关键字在待排表中的位置):"<<endl;
for(int u=level-1;u>=0;u--){
for(int i=0;i<level_count[u];i++)
cout<<"("<<level_point[u][i].key<<"-"<<level_point[u][i].pos<<") ";
cout<<endl;
}
//第一次树形排序的最小值和最小位置
int cur_min_key=level_point[level-1][0].key;
int cur_min_pos=level_point[level-1][0].pos;
sorted_keys[0]=cur_min_key;
//输出剩下size-1个最小的数
for(int count=1;count<=size-1;count++){
level_point[0][cur_min_pos].key=MAX_INT;
//找到需要重新比较的两个位置
int a_pos=cur_min_pos;
int b_pos=a_pos%2==0 ? a_pos+1 : a_pos-1;
for(int m=1;m<level;m++){
if(b_pos>=level_count[m-1]){
level_point[m][a_pos/2].key=level_point[m-1][a_pos].key;
level_point[m][a_pos/2].pos=level_point[m-1][a_pos].pos;
}else{
level_point[m][a_pos/2].key=level_point[m-1][a_pos].key<=level_point[m-1][b_pos].key ? level_point[m-1][a_pos].key : level_point[m-1][b_pos].key;
level_point[m][a_pos/2].pos=level_point[m-1][a_pos].key<=level_point[m-1][b_pos].key ? level_point[m-1][a_pos].pos : level_point[m-1][b_pos].pos;
}
a_pos=a_pos/2;
b_pos=a_pos%2==0 ? a_pos+1 : a_pos-1;
}
//记录每一次树形排序的最小值和对应的位置
cur_min_key=level_point[level-1][0].key;
cur_min_pos=level_point[level-1][0].pos;
sorted_keys[count]=cur_min_key;
//打印第count次的树形选择排序:
cout<<"第"<<(count+1)<<"次树形选择排序 (关键字 - 关键字在待排表中的位置):"<<endl;
for(int u=level-1;u>=0;u--){
for(int i=0;i<level_count[u];i++)
cout<<"("<<level_point[u][i].key<<"-"<<level_point[u][i].pos<<") ";
cout<<endl;
}
}
//打印排序好的序列
cout<<endl<<endl<<"排序序列:";
for(int k=0;k<size;k++)
cout<<sorted_keys[k]<<" ";
cout<<endl;
free(level_count);
free(sorted_keys);
freeAll(level_point,level);
}
//Test
void main(){
int raw[]={49,38,65,97,76,13,27,49};
int size=sizeof(raw)/sizeof(int);
inc_sort(raw,size);
}
树形选择排序需要建立一棵含n个叶子结点的完全二叉树,其深度为[logN]+1。因此,除第一次排序需要比较n次以外,其余每一次树形选择排序都只需要比较logN次。因此树形选择排序的时间复杂度为O(N*logN) 。但是这种排序方法大量额外的空间,一棵n个叶子结点的满二叉树有2n-1个结点。则对N个关键字的树形选择排序需要近2N左右的结点。空间复杂度为O(2N) 。该方法也是稳定的排序 。
树形选择排序仍然有很多缺点,比如空间代价高,需要和无穷大关键字做比较等。为了弥补,J.willioms在1964年提出了下面的另一种选择排序——堆排序。
(3) 堆排序
堆的定义如如下:n个元素的序列{K0 ... K(n-1)},当且仅当满足下关系时,称之为堆。(注: 序列从下标0作为第一个元素开始)
ki <= k(2i+1) && ki <= k(2i+2) —— 小顶堆
ki >= k(2i+1) && ki >= k(2i+2) —— 大顶堆
若将此序列对应的一维数组(序列的内存结构)看成是一个完全二叉树,即Ki 的左孩子是K(2i+1),右孩子是K(2i+2)。则堆的含义就是,完全二叉树中所有非终结点的值均不大于(不小于)其左、右孩子结点的值。因此,堆顶元素K0就是整个序列的最小值了。
堆排序的算法流程:
首先,将待排序列整理成堆。即从序列的第[n/2]-1个元素(完全二叉树最后一个非终结点)开始,到第0个结点为止调整堆。具体过程见下图:

然后,输出堆顶元素K0后,用当前堆中最后一个元素K(n-1)代替堆顶。并将待排序列减少一个(最后一个元素已经移到了第0号位置),接着调整堆,即将移动后的堆顶元素向下调整(保证小顶堆)。具体过程如下图:

最后,依次循环下去,直到输出序列的全部元素为止。
#include<iostream.h>
/*********************
* 堆排序 Heap Sort *
*********************/
class HeapSort{
public:
//递增排序
static void inc_sort(int keys[], int size);
private:
//创建堆
static void create(int keys[],int size);
//调整堆
static void adjust(int keys[],int var_size);
//交换
static void swap(int keys[],int pos_a,int pos_b);
};
//创建堆
void HeapSort :: create(int keys[],int size){
for(int i=(size-1)/2;i>=0;i--){
int lchild=i*2+1;
int rchild=i*2+2;
while(lchild<size){
int next_pos=-1;
if(rchild>=size&&keys[i]>keys[lchild]){
HeapSort ::swap(keys,i,lchild);
next_pos=lchild;
}
if(rchild<size){
int min_temp=keys[lchild]<=keys[rchild] ? keys[lchild] : keys[rchild];
int min_pos=keys[lchild]<=keys[rchild] ? lchild : rchild;
if(keys[i]>keys[min_pos]){
swap(keys,i,min_pos);
next_pos=min_pos;
}
}
if(next_pos==-1) break;
lchild=next_pos*2+1;
rchild=next_pos*2+2;
}
}
}
//调整堆
void HeapSort :: adjust(int keys[],int var_size){
int pos=0;
while((pos*2+1)<var_size){
int next_pos=-1;
if((pos*2+2)>=var_size&&keys[pos]>keys[pos*2+1]){
swap(keys,pos,pos*2+1);
next_pos=pos*2+1;
}
if((pos*2+2)<var_size){
int min_keys=keys[pos*2+1]<=keys[pos*2+2] ? keys[pos*2+1] : keys[pos*2+2];
int min_pos=keys[pos*2+1]<=keys[pos*2+2] ? (pos*2+1) : (pos*2+2);
if(keys[pos]>min_keys){
swap(keys,pos,min_pos);
next_pos=min_pos;
}
}
if(next_pos==-1) break;
pos=next_pos;
}
}
//递增排序
void HeapSort :: inc_sort(int keys[], int size){
HeapSort::create(keys,size);
int var_size=size;
while(var_size>0){
cout<<keys[0]<<" "; //Êä³öÿһÂÖ¶ÑÅÅÐòµÄ×îСֵ
keys[0]=keys[var_size-1];
--var_size;
adjust(keys,var_size);
}
}
//keys[pos_a] <-> keys[pos_b]
void HeapSort :: swap(int keys[],int pos_a,int pos_b){
int temp=keys[pos_a];
keys[pos_a]=keys[pos_b];
keys[pos_b]=temp;
}
//Test HeapSort
void main(){
int raw[]={49,38,65,97,76,13,27,49};
int size=sizeof(raw)/sizeof(int);
HeapSort::inc_sort(raw,size);
}
堆排序方法对记录较少的文件效果一般,但对于记录较多的文件还是很有效的。其运行时间主要耗费在创建堆和反复调整堆上。堆排序即使在最坏情况下,其时间复杂度也为O(N*logN) 。这一点比快速排序 要好。另外,堆排序所需要的空间复杂度为O(1) 。但却是不稳定排序 。
发表评论
-
★经典问题—链表中的环问题
2010-06-29 14:43 4511转载:http://www.cppblog.com ... -
★经典问题—元素选择问题
2010-05-24 10:53 3412元素选择问题 : 给定线性序集中n个元素和一个整数k( ... -
【串和序列处理 8】最长平台问题
2010-04-28 16:41 38431、经典最长平台算法 已知一个已经从小到大 ... -
【排序结构7】 基数排序
2010-04-20 16:17 4665《桶排序 》中我们能够看到,数据值的范围越大,可能需要桶的个 ... -
【排序结构6】 桶排序
2010-04-19 20:28 23294从《基于比较的排序结构总结 》中我们知道:全依赖“比较”操作的 ... -
【排序结构5】 基于比较的内部排序总结
2010-04-18 16:15 6850★ 基于“比较”操作的内部排序性能大PK ... -
【排序结构4】 归并排序
2010-04-17 16:29 3387归并排序 O(N*logN) 是另一种效率很高的排序方法。&q ... -
【排序结构2】交换排序
2010-04-14 11:04 27201、起泡排序 O(N^2) ... -
【排序结构1】插入排序
2010-04-13 17:11 31231、基本概念介绍 (1) 如果待排序列中有两个 ... -
【串和序列处理 7】LIS 最长递增子序列
2010-03-25 16:37 5903LIS: 给定一个字符串序列S={x0,x1,x2,.. ... -
【串和序列处理 6】LCS 最长公共子序列
2010-03-23 17:38 8942LCS:又称 最长公共子序列。 其中子序列(subse ... -
【串和序列处理 5】KMP子串匹配算法
2010-03-22 19:59 9278模式匹配: 在字符串 ... -
★经典问题—欧几里得求最大公约数
2010-03-20 19:21 3480问题:快速求取正整数a,b的最大公约数? ... -
【串和序列处理 4】Suffix Trie 子串匹配结构
2010-03-20 15:15 9264Suffix Trie : 又称后 ... -
【串和序列处理 3】Trie Tree 串集合查找
2010-03-18 13:40 17891Trie 树, 又称字典树,单词查找树。它来源于retr ... -
【串和序列处理 2】字符串编辑距离算法
2010-03-15 08:45 11162我们来看一个实际应用。现代搜索技术的发展很多以提供优质、高效的 ... -
【串和序列处理 1】PAT Tree 子串匹配结构
2010-03-14 19:10 11408Patricia Tree 简称PAT tree ... -
【查找结构6】动态查找树比较
2010-03-12 13:32 11429我们这个专题介绍的动态查找树主要有: 二叉查找树(BST),平 ... -
【查找结构4】红黑树 [RBT]
2010-03-10 10:58 10913大部分转载:http://yanglongylj.blog.1 ... -
【查找结构5】多路查找树/B~树/B+树
2010-03-09 11:56 18350在前面专题中讲的BST、A ...



相关推荐
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
【数据结构 - 排序算法详解】 排序是计算机科学中不可或缺的一部分,主要目的是将无序的数据转换成有序的形式,以方便后续的处理和查询。在本文中,我们将深入探讨四种常见的内部排序方法:插入排序、快速排序、...
数据结构课程设计直接选择排序 数据结构课程设计直接选择排序 数据结构课程设计直接选择排序 数据结构课程设计直接选择排序 数据结构课程设计直接选择排序 数据结构课程设计直接选择排序 数据结构课程设计直接选择...
这两种排序算法在数据结构和算法的学习中占据着核心地位,因为它们帮助初学者理解排序的基本原理。 首先,我们来看**插入排序(Insertion Sort)**。插入排序是一种简单直观的排序算法,它的工作方式类似于人们整理...
### 数据结构之简单选择排序详解 #### 知识点一:简单选择排序的基本概念与原理 简单选择排序是一种基本的排序算法,其工作原理是通过不断地寻找剩余未排序元素中的最小值(或最大值),并将它放到已排序序列的...
3. **冒泡排序**: 冒泡排序是一种简单的交换排序,通过不断比较相邻元素并交换位置,使得最大(或最小)的元素逐渐“浮”到序列末尾。虽然冒泡排序的时间复杂度较高,但在最佳情况下(已排序的数组)其效率与插入...
在编程领域,排序算法是数据结构与算法学习中的基础部分,它们用于整理无序的数据序列。以下是关于"冒泡排序,选择排序,插入排序,希尔排序,堆排序,归并排序,快速排序"这七种常见排序算法的源码实现及相关知识点...
直接选择排序和希尔排序是两种不同的排序算法,它们在计算机科学和编程中有着重要的应用,尤其是在数据结构和算法的学习中。下面将详细讲解这两种排序算法的原理、实现方式以及它们在C++语言中的具体实现。 **直接...
根据提供的文件信息,我们可以深入探讨几种经典的排序...而对于大规模数据集,快速排序通常是更好的选择。此外,希尔排序通过引入增量序列,能够在一定程度上改善插入排序的时间复杂度,尤其是在数据量较大时表现更优。
3. 选择排序:每次从未排序的部分中找出最小(或最大)的元素,放到已排序部分的末尾。经过n-1次这样的操作,整个数组就被排序了。选择排序不保证每一步都是最优的,但其交换次数较少。 4. 归并排序:同样基于分治...
### 数据结构排序实验报告知识点解析 #### 实验背景与目的 - **实验背景**:本实验报告来源于南昌大学科学技术学院信息学科部计算机系的一次专业课程实验。《数据结构》作为一门重要的计算机基础课程,其目的在于...
3. **合并法排序(Merge Sort)**: - 基本思想:采用分治策略,将大问题分解为小问题来解决。首先将待排序的序列分为两半,对每半分别进行排序,然后合并两个已排序的子序列。递归地执行这个过程,直到子序列只有...
首先,堆排序是一种基于比较的排序算法,利用了二叉堆的数据结构。二叉堆是一个完全二叉树,可以分为最大堆或最小堆,其中每个父节点的值都大于或等于其子节点。堆排序的过程包括构建初始堆和调整堆。首先,将无序...
3. **选择排序**:选择排序每次从未排序的部分选取最小(或最大)的元素,放到已排序部分的末尾。该算法不保证稳定性,但其交换次数固定,适合处理数据量较小的情况。 4. **堆排序**:堆排序利用了堆这种数据结构。...
数据结构中的排序算法是计算机科学中的重要概念,用于组织和管理数据,提高数据访问和...总的来说,理解和实现这些排序算法对于提升编程技能和深入理解数据结构有重要意义,也有助于在实际项目中选择合适的排序方法。
在这个数据结构报告中,我们将深入探讨七种不同的内排序算法:简单选择排序、冒泡排序、插入排序、快速排序、两路合并排序以及堆排序。这些排序算法在C++语言环境下进行了实现,并且包含了详细的源代码和实验报告,...
7. 简单选择排序:对于顺序表{2,3,1,3',2'},经过1趟排序后变成{1,3,2,3',2'},3趟后可能变成{1,2,2',3,3'}。 8. 稳定排序算法:直接插入排序是稳定的,而快速排序、希尔排序和堆排序都是不稳定的。 9. 某趟结束后...
3. **排序表的存储结构**: ```c struct records { keytype key; // 关键字类型 fields other; // 其他字段 }; typedef records LIST[maxsize]; // 定义最大长度为maxsize的数组 ``` #### 二、排序的稳定性 ...
3. **选择排序**: 选择排序每次从未排序的序列中找到最小(或最大)的元素,然后放到已排序序列的末尾。这个过程重复进行,直到所有元素都在正确的位置上。简单选择排序的时间复杂度为O(n^2),而堆排序是选择排序...
在链表中实现这两种排序方法时,需要考虑链表节点的结构和指针操作。链表的特性使得我们不能像数组那样直接通过下标访问元素,而是需要通过指针来遍历和修改节点。因此,实现链表排序时,我们需要额外处理节点的连接...