微商城网站建设公司的价格,玩具外贸好做吗,广州设计网站培训班,深圳网站设计公司电话简单选择排序
选择排序是一种简单直观的排序算法。首先在未排序序列中找到最大#xff08;最小#xff09;的元素#xff0c;存放到排序学列的其实位置#xff0c;然后在剩余的未排序的元素中寻找最小#xff08;最大#xff09;元素#xff0c;存放在已排序序列的后面…简单选择排序
选择排序是一种简单直观的排序算法。首先在未排序序列中找到最大最小的元素存放到排序学列的其实位置然后在剩余的未排序的元素中寻找最小最大元素存放在已排序序列的后面
算法步骤
在未排序序列中找到最大小元素存放在排序序列的起始位置再从剩余的未排序序列中找到最大小元素然后存放在已排序序列的后面重复上诉第二步骤直至排序结束
算法理解
例如对无序表{5612809120}采用简单选择排序算法进行排序具体过程为 第一次遍历时从下标为 1 的位置即 56 开始找出关键字值最小的记录 12同下标为 0 的关键字 56 交换位置 第二次遍历时从下标为 2 的位置即 56 开始找出最小值 20同下标为 2 的关键字 56 互换位置 第三次遍历时从下标为 3 的位置即 80 开始找出最小值 56同下标为 3 的关键字 80 互换位置 第四次遍历时从下标为 4 的位置即 91 开始找出最小是 80同下标为 4 的关键字 91 互换位置 到此简单选择排序算法完成无序表变为有序表。
代码实现
#include iostream
using namespace std;#define MAX 9
//单个记录的结构体
typedef struct {int key;
}SqNote;
//记录表的结构体
typedef struct {SqNote r[MAX];int length;
}SqList;
//交换两个记录的位置
void swap(SqNote *a,SqNote *b){int keya-key;a-keyb-key;b-keykey;
}
//查找表中关键字的最小值
int SelectMinKey(SqList *L,int i){int mini;//从下标为 i1 开始一直遍历至最后一个关键字找到最小值所在的位置while (i1L-length) {if (L-r[min].keyL-r[i1].key) {mini1;}i;}return min;
}
//简单选择排序算法实现函数
void SelectSort(SqList * L){for (int i0; iL-length; i) {//查找第 i 的位置所要放置的最小值的位置int jSelectMinKey(L,i);//如果 j 和 i 不相等说明最小值不在下标为 i 的位置需要交换if (i!j) {swap((L-r[i]),(L-r[j]));}}
}
int main() {SqList *L new SqList;L-length8;L-r[0].key49;L-r[1].key38;L-r[2].key65;L-r[3].key97;L-r[4].key76;L-r[5].key13;L-r[6].key27;L-r[7].key49;SelectSort(L);for (int i0; iL-length; i) {cout L-r[i].key ;}return 0;
}代码实现
13 27 38 49 49 65 76 97树形选择排序
树形选择排序又称“锦标赛排序”是一种按照锦标赛的思想进行选择排序的方法即所有记录采取两两分组筛选出较小较大的值然后从筛选出的较小较大值中再两两分组选出更小更大值依次类推直到最后选出一个最小最大值。同样可以采用此方式筛选出次小次大值等
算法理解
整个排序的过程可以用一棵具有 n 个叶子结点的完全二叉树表示。例如对无序表{4938659776132749}采用树形选择的方式排序过程如下
首先将无序表中的记录采用两两分组筛选出各组中的较小值如图 1 中的a过程然后将筛选出的较小值两两分组筛选出更小的值以此类推如图 1 中的bc过程最终整棵树的根结点中的关键字即为最小关键字 图 1 树形选择排序一 筛选出关键字 13 之后继续重复此方式找到剩余记录中的最小值此时由于关键字 13 已经筛选完成需要将关键字 13 改为“最大值”继续重复此过程如图 2 所示 图 2 树形选择排序二
通过不断地重复此过程可依次筛选出从小到大的所有关键字。该算法的时间复杂度为O(nlogn)同简单选择排序相比该算法减少了不同记录之间的比较次数但是程序运行所需要的空间较多。
代码实现
#include iostream
using namespace std;
#define N 8
void TreeSelectionSort(int *mData)
{int MinValue 0;int tree[N * 4]; // 树的大小int max, maxIndex, treeSize;int i, n N, baseSize 1;while (baseSize n)baseSize * 2;treeSize baseSize * 2 - 1;for (i 0; i n; i) {//将要排的数字填到树上tree[treeSize - i] mData[i];}for (; i baseSize; i) {//其余的地方都填上最小值tree[treeSize - i] MinValue;}// 构造一棵树大的值向上构造for (i treeSize; i 1; i - 2){tree[i / 2] (tree[i] tree[i - 1] ? tree[i] : tree[i - 1]);}n - 1;while (n ! -1){max tree[1]; //树顶为最大值mData[n--] max; //从大到小倒着贴到原数组上maxIndex treeSize; //最大值下标while (tree[maxIndex] ! max) {maxIndex--;}//找最大值下标tree[maxIndex] MinValue;while (maxIndex 1) {if (maxIndex % 2 0) {tree[maxIndex / 2] (tree[maxIndex] tree[maxIndex 1] ? tree[maxIndex] : tree[maxIndex 1]);}else {tree[maxIndex / 2] (tree[maxIndex] tree[maxIndex - 1] ? tree[maxIndex] : tree[maxIndex - 1]);}maxIndex / 2;}}
}
int main()
{int a[N] {49,38,65,97,76,13,27,49};TreeSelectionSort(a);for (int i 0; i N; i) {cout a[i] ;}return 0;
}运行结果
13 27 38 49 49 65 76 97堆排序
堆排序 ( H e a p s o r t ) (Heapsort) (Heapsort)是指利用堆来实现的一种排序算法。堆积是一个近似完全二叉树的结构并同时满足堆积的性质即子结点的键值或索引总是小于或者大于它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。堆排序的平均时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)。分为两种方法
大顶堆每个节点的值都大于或等于其子节点的值在堆排序算法中用于升序排列小顶堆每个节点的值都小于或等于其子节点的值在堆排序算法中用于降序排列 算法思想
了解了堆的基本性质之后我们就可以看堆排序的基本思想。
将未排序的序列构造成大或者小顶堆根据堆的性质我们可以找到序列中的最大或者最小值把堆首和堆尾互换并把堆的大小减 1 1 1重复上面的步骤直到堆的大小为 1 1 1 代码实现
#include iostream
using namespace std;
#define MAX 9
//单个记录的结构体
typedef struct {int key;
}SqNote;
//记录表的结构体
typedef struct {SqNote r[MAX];int length;
}SqList;
//将以 r[s]为根结点的子树构成堆堆中每个根结点的值都比其孩子结点的值大
void HeapAdjust(SqList * H,int s,int m){SqNote rcH-r[s];//先对操作位置上的结点数据进行保存放置后序移动元素丢失。//对于第 s 个结点筛选一直到叶子结点结束for (int j2*s; jm; j*2) {//找到值最大的孩子结点if (j1m (H-r[j].keyH-r[j1].key)) {j;}//如果当前结点比最大的孩子结点的值还大则不需要对此结点进行筛选直接略过if (!(rc.keyH-r[j].key)) {break;}//如果当前结点的值比孩子结点中最大的值小则将最大的值移至该结点由于 rc 记录着该结点的值所以该结点的值不会丢失H-r[s]H-r[j];sj;//s相当于指针的作用指向其孩子结点继续进行筛选}H-r[s]rc;//最终需将rc的值添加到正确的位置
}
//交换两个记录的位置
void swap(SqNote *a,SqNote *b){int keya-key;a-keyb-key;b-keykey;
}
void HeapSort(SqList *H){//构建堆的过程for (int iH-length/2; i0; i--) {//对于有孩子结点的根结点进行筛选HeapAdjust(H, i, H-length);}//通过不断地筛选出最大值同时不断地进行筛选剩余元素for (int iH-length; i1; i--) {//交换过程即为将选出的最大值进行保存大表的最后同时用最后位置上的元素进行替换为下一次筛选做准备swap((H-r[1]), (H-r[i]));//进行筛选次最大值的工作HeapAdjust(H, 1, i-1);}
}int main() {SqList *L new SqList ;L-length8;L-r[1].key49;L-r[2].key38;L-r[3].key65;L-r[4].key97;L-r[5].key76;L-r[6].key13;L-r[7].key27;L-r[8].key49;HeapSort(L);for (int i1; iL-length; i) {cout L-r[i].key ;}return 0;
}运行结果
13 27 38 49 49 65 76 97注意堆排序相对于树形选择排序其只需要一个用于记录交换rc的辅助存储空间比树形选择排序的运行空间更小。
