六种排序算法的算法逻辑

Ⅰ 面试必会八大排序算法（Python）

一、插入排序

介绍

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。

算法适用于少量数据的排序，时间复杂度为O(n^2)。

插入排算法是稳定的排序方法。

步骤

①从第一个元素开始，该元素可以认为已经被排序

②取出下一个元素，在已经排序的元素序列中从后向前扫描

③如果该元素（已排序）大于新元素，将该元素移到下一位置

④重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

⑤将新元素插入到该位置中

⑥重复步骤2

排序演示

算法实现

二、冒泡排序

介绍

冒泡排序（Bubble Sort）是一种简单的排序算法，时间复杂度为O(n^2)。

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

原理

循环遍历列表，每次循环找出循环最大的元素排在后面；

需要使用嵌套循环实现：外层循环控制总循环次数，内层循环负责每轮的循环比较。

步骤

①比较相邻的元素。如果第一个比第二个大，就交换他们两个。

②对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

③针对所有的元素重复以上的步骤，除了最后一个。

④持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

算法实现：

三、快速排序

介绍

快速排序（Quicksort）是对冒泡排序的一种改进，借用了分治的思想，由C. A. R. Hoare在1962年提出。

基本思想

快速排序的基本思想是：挖坑填数 + 分治法。

首先选出一个轴值(pivot，也有叫基准的)，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

实现步骤

①从数列中挑出一个元素，称为 “基准”（pivot）；

②重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）；

③对所有两个小数列重复第二步，直至各区间只有一个数。

排序演示

算法实现

四、希尔排序

介绍

希尔排序（Shell Sort）是插入排序的一种，也是缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法，时间复杂度为：O(1.3n)。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

·插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率；

·但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位。

基本思想

①希尔排序是把记录按下标的一定量分组，对每组使用直接插入算法排序；

②随着增量逐渐减少，每组包1含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法被终止。

排序演示

算法实现

五、选择排序

介绍

选择排序(Selection sort)是一种简单直观的排序算法，时间复杂度为Ο(n2)。

基本思想

选择排序的基本思想：比较 + 交换。

第一趟，在待排序记录r1 ~ r[n]中选出最小的记录，将它与r1交换；

第二趟，在待排序记录r2 ~ r[n]中选出最小的记录，将它与r2交换；

以此类推，第 i 趟，在待排序记录ri ~ r[n]中选出最小的记录，将它与r[i]交换,使有序序列不断增长直到全部排序完毕。

排序演示

选择排序的示例动画。红色表示当前最小值，黄色表示已排序序列，蓝色表示当前位置。

算法实现

六、堆排序

介绍

堆排序（Heapsort）是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。

利用数组的特点快速指定索引的元素。

基本思想

堆分为大根堆和小根堆，是完全二叉树。

大根堆的要求是每个节点的值不大于其父节点的值，即A[PARENT[i]] >=A[i]。

在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

排序演示

算法实现

七、归并排序

介绍

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

基本思想

归并排序算法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

算法思想

自上而下递归法（假如序列共有n个元素）

① 将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素；

② 将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素；

③ 重复步骤②，直到所有元素排序完毕。

自下而上迭代法

① 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

② 设定两个指针，最初位置分别为两个已经排序序列的起始位置；

③ 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

④ 重复步骤③直到某一指针达到序列尾；

⑤ 将另一序列剩下的所有元素直接复制到合并序列尾。

排序演示

算法实现

八、基数排序

介绍

基数排序（Radix Sort）属于“分配式排序”，又称为“桶子法”。

基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m) ，其中 r 为采取的基数，而m为堆数。

在某些时候，基数排序法的效率高于其他的稳定性排序法。

基本思想

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

基数排序按照优先从高位或低位来排序有两种实现方案：

MSD（Most significant digital） 从最左侧高位开始进行排序。先按k1排序分组, 同一组中记录, 关键码k1相等,再对各组按k2排序分成子组, 之后, 对后面的关键码继续这样的排序分组, 直到按最次位关键码kd对各子组排序后. 再将各组连接起来,便得到一个有序序列。MSD方式适用于位数多的序列。

LSD （Least significant digital）从最右侧低位开始进行排序。先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。LSD方式适用于位数少的序列。

排序效果

算法实现

九、总结

各种排序的稳定性、时间复杂度、空间复杂度的总结：

平方阶O(n²)排序：各类简单排序：直接插入、直接选择和冒泡排序；

从时间复杂度来说：

线性对数阶O(nlog₂n)排序：快速排序、堆排序和归并排序；

O(n1+§))排序，§是介于0和1之间的常数：希尔排序 ；

线性阶O(n)排序：基数排序，此外还有桶、箱排序。

Ⅱ 八大经典排序算法原理及实现

该系列文章主要是记录下自己暑假这段时间的学习笔记，暑期也在实习，抽空学了很多，每个方面的知识我都会另起一篇博客去记录，每篇头部主要是另起博客的链接。

冒泡排序算法应该是大家第一个接触的算法，其原理都应该懂，但我还是想以自己的语言来叙述下其步奏：

按照计算时间复杂度的规则，去掉常数、去掉最高项系数，其复杂度为O(N^2)
冒泡排序及其复杂度分析

空间复杂度就是在交换元素时那个临时变量所占的内存

给定一个整数序列{6,1,2,3,4},每完成一次外层循环的结果为：

我们发现第一次外层循环之后就排序成功了，但是还是会继续循环下去，造成了不必要的时间复杂度，怎么优化？

冒泡排序都是相邻元素的比较，当相邻元素相等时并不会交换，因此冒泡排序算法是稳定性算法

插入排序是对冒泡排序的一种改进

插入排序的思想是数组是部分有序的，再将无序的部分插入有序的部分中去,如图：
（图片来自 这里 ）

空间复杂度就是在交换元素时那个临时变量所占的内存

插入排序的优化，有两种方案：

文章后面会给出这两种排序算法

由于插入排序也是相邻元素的比较，遇到相等的相邻元素时不会发生交换，也不会造成相等元素之间的相对位置发生变化

其原理是从未排序的元素中选出最小值(最大值)放在已排序元素的后面

空间复杂度就是在交换元素时那个临时变量所占的内存

选择排序是不稳定的，比如 3 6 3 2 4，第一次外层循环中就会交换第一个元素3和第四个元素2，那么就会导致原序列的两个3的相对位置发生变化

希尔排序算是改良版的插入排序算法，所以也称为希尔插入排序算法

其原理是将序列分割成若干子序列（由相隔某个 增量 的元素组成的），分别进行直接插入排序；接着依次缩小增量继续进行排序，待整个序列基本有序时，再对全体元素进行插入排序，我们知道当序列基本有序时使用直接插入排序的效率很高。
上述描述只是其原理，真正的实现可以按下述步奏来：

希尔排序的效率取决于 增量值gap 的选取，这涉及到数学上尚未解决的难题，但是某些序列中复杂度可以为O(N 1.3)，当然最好肯定是O(N)，最坏是O(N 2)

空间复杂度就是在交换元素时那个临时变量所占的内存

希尔排序并不只是相邻元素的比较，有许多跳跃式的比较，难免会出现相同元素之间的相对位置发生变化，所以希尔排序是不稳定的

理解堆排序，就必须得先知道什么是堆？

二叉树的特点：

当父节点的值总是大于子结点时为 最大堆 ；反之为 最小堆 ，下图就为一个二叉堆

一般用数组来表示堆，下标为 i 的结点的父结点下标为(i-1)/2；其左右子结点分别为 (2 i + 1)、(2 i + 2)

怎么将给定的数组序列按照堆的性质，调整为堆？

这里以建立最小堆为示例，

很明显对于其叶子结点来说，已经是一个合法的子堆，所以做堆调整时，子节点没有必要进行，这里只需从结点为A[4] = 50的结点开始做堆调整，即从（n/2 - 1）位置处向上开始做堆调整：

由于每次重新恢复堆的时间复杂度为O(logN)，共N - 1次重新恢复堆操作，再加上前面建立堆时N / 2次向下调整，每次调整时间复杂度也为O(logN)，二次操作时间相加还是O(N logN)。故堆排序的时间复杂度为O(N * logN)。

空间复杂度就是在交换元素时那个临时变量所占的内存

由于堆排序也是跨越式的交换数据，会导致相同元素之间的相对位置发生变化，则算法不稳定。比如 5 5 5 ,堆化数组后将堆顶元素5与堆尾元素5交换，使得第一个5和第三个5的相对位置发生变化

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

快速排序在应该是大家经常看到、听到的算法，但是真正默写出来是有难度的。希望大家看了下面 挖坑填数 方法后，能快速写出、快速排序。

其原理就这么几句话，但是现实起来并不是这么简单，我们采取流行的一种方式 挖坑填数分治法

对于序列： 72 6 57 88 60 42 83 73 48 85

数组变为： 48 6 57 88 60 42 83 73 88 85
再重复上面的步骤，先从后向前找，再从前向后找：

数组变为： 48 6 57 42 60 72 83 73 88 85
可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了

空间复杂度，主要是递归造成的栈空间的使用:

快速排序的优化主要在于基准数的选取

快速排序也是跨越式比较及交换数据，易导致相同元素之间的相对位置发生变化，所以快速排序不稳定

前面也说了二分查找排序是改进的插入排序，不同之处在于，在有序区间查找新元素插入位置时，为了减少比较次数提高效率，采用二分查找算法进行插入位置的确定
具体步骤，设数组为a[0…n]：

二分查找插入位置，因为不是查找相等值，而是基于比较查插入合适的位置，所以必须查到最后一个元素才知道插入位置。
二分查找最坏时间复杂度：当2^X>=n时，查询结束，所以查询的次数就为x，而x等于log2n（以2为底，n的对数）。即O(log2n)
所以，二分查找排序比较次数为：x=log2n
二分查找插入排序耗时的操作有：比较 + 后移赋值。时间复杂度如下：

二分查找排序在交换数据时时进行移动，当遇到有相等值插入时也只会插入其后面，不会影响其相等元素之间的相对位置，所以是稳定的

白话经典算法排序
冒泡排序选择排序
快速排序复杂度分析
优化的插入排序

Ⅲ 我对几种常见排序算法的理解

排序算法一般分为以下几种： （1）非线性时间比较类排序：交换类排序（快速排序和冒泡排序）、插入类排序（简单插入排序和希尔排序）、选择类排序（简单选择排序和堆排序）、归并排序（二路归并排序和多路归并排序）；（2）线性时间非比较类排序：计数排序、基数排序和桶排序。

Ⅳ 谁教我：数据结构的各种排序

1.快速排序

#include"stdio.h"
#define N 100
int a[N]={0};//存放要排序的数

int Qsort(int m,int n)//对数组中m到n的元素进行快速排序
{
int p,q;
int head,sign;
if(m!=n)//选定的数列不止一个元素
{
head=a[n];//选择数列的末尾元素作为比较元素
p=m;//p标记数列的首元素
q=n-1;//标记末尾元素的前一个元素
sign=n;//记录比较元素的位置，以其作为空位置
while(p<=q)//分别比较p、q所标记的元素与比较元素的大小，比其小的放在左边，比其大的放在右边
{
while(a[p]<head)//p所指元素比比较元素小，p右移
{
p++;
if(p>q)
{
break;
}
}
a[sign]=a[p];//将p所指元素移入空位置
sign=p;//记录空余位置
p++;
if(p>q)
{
break;
}
while(a[q]>head)//q所指元素比比较元素大，q左移
{
q--;
if(p>q)
{
break;
}
}
a[sign]=a[q];
sign=q;
q--;
}
a[sign]=head;//比较完成后，将比较元素移入空位置
if(sign-1>m)
{
Qsort(m,sign-1);//对m到sign-1的数列进行排序
}
if(sign+1<n)
{
Qsort(sign+1,n);//对sign+1到n的数列进行排序
}
}
return(1);
}

int Print(int m,int n)//对m到n的数组序列输出
{
int i;
for(i=m;i<=n;i++)
{
printf("%d\n",a[i]);
}
return(1);
}

int main()
{
int n,i;
scanf("%d",&n);//输入将要排序的数的个数
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);//输入要排序的数
}
Qsort(0,n-1);
Print(0,n-1);
}
二、 详细设计：重要函数中的算法设计，实现流程，传递参数的说明；

三、调试分析与心得体会：
快速排序的思想时从数组序列中选定一个元素，将序列中其余元素与其进行比较，将比其小的放在左边，比其大的放在右边，然后以比较元素为中点，将序列分成两部分，再将它们分别进行快速排序，依次类推，直到序列中只有一个元素为止。

2.合并排序

#include"stdio.h"
#define N 10000
int a[N];//用a数组记录所给无序数列
int b[N]={0};//用b数组记录每次排序之后的a数组
int sign=0;
void Merge(int m,int mid,int n)//将两个有序数列合并成为一个有序数列
{
int i,j,k;
i=k=m;
j=mid+1;
while(i<=mid&&j<=n)//依次比较两个有序数列中的元素，从大到小将其放入b数组相应位置中
{
if(a[i]<a[j])
{
b[k]=a[i];
k++;
i++;
}
else
{
b[k]=a[j];
k++;
j++;
}
}
if(i<=mid)//将比较之后的剩余元素放入b数组相应位置
{
while(i<=mid)
{
b[k]=a[i];
k++;
i++;
}
}
else
{
while(j<=n)
{
b[k]=a[j];
k++;
j++;
}
}
for(i=m;i<=n;i++)//将合并后的数列重新放入a数组相应位置
{
a[i]=b[i];
}
}
int Msort(int m,int n)//对所给无序数列进行排序
{
int mid;
if(n!=m)
{
mid=(n+m)/2; //将数列一分为二直到其只有一个元素
Msort(m,mid);
Msort(mid+1,n);
Merge(m,mid,n);//将分割后的数列重新合并起来
}
return(1);
}
void Print(int num)//将序列依次输出
{
int i;
for(i=0;i<num;i++)
{
printf("%d\n",a[i]);
}
}
int main()
{
int sign;
int i;
int num;
scanf("%d",&num);//输入将要排序的数的个数
for(i=0;i<num;i++)
{
scanf("%d",&a[i]);//依次输入要排序的数
}
sign=Msort(0,num-1);
Print(num);//输出完成排序后的有序数列
}
二、 详细设计：重要函数中的算法设计，实现流程，传递参数的说明；
三、调试分析与心得体会：
合并排序是排序的一种常用方法，其主要思想为：将一个无序数列依次分割直到其每个序列只有一个元素为止，然后再将两个序列合并为一个有序数列，依此类推。

3.我的数据结构实验课题（关于排序）

//问题描述：排序器
//要 求：实现以下六种排序算法，将给定的不同规模大小的数据文件（data01.txt，data02.txt，data03.txt，data04.txt）进行排序，
//并将排序结果分别存储到sorted01.txt，sorted02.txt，sorted03.txt和sorted04.txt文件中。
//1）、Shell排序； 2）、Quick排序
//3）、锦标赛排序； 4）、堆排序
//5）、归并排序； 6）、基数排序
//在实现排序算法1）~4）时，统计数据元素比较的次数和交换的次数，进而对这四种算法在特定数据条件下的效率进行分析和评判。

#include"stdio.h"
#include"math.h"
#include"stdlib.h"
#include"malloc.h"
#define Maxsize 10000000
#define N 20
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
#define LEN sizeof(SqList)
#define Maxr 10
#define MAXNUM 100000000

typedef struct node{
int key;
int num;
};
typedef struct {
struct node r[Maxsize+1];
long length;
}SqList,*qSqList;
typedef struct node2{
struct node r;
struct node2 *next;
}RecType;
long shifttimes;//统计移动次数
long comparetimes;//统计比较次数

qSqList creat(char filename[])//读入文件并且将数据保存
{
FILE *fp;
long i;
qSqList L;
L=(qSqList)malloc(LEN);
L->length=0;
if((fp=fopen(filename,"r"))==NULL)//文件不存在时终止程序
{
printf("cannot open file\n");
exit(0);
}
for(i=1;i<Maxsize+1;i++)
{
fscanf(fp,"%ld (%d)",&(L->r[i].key),&(L->r[i].num));
if(L->r[i].key<0)
break;
L->length++;//记录读入的数据长度
}
fclose(fp);
return(L);
}

void Print2(qSqList L)//将序列输出到指定的文件中
{
long i;
FILE *fp;
char filename[N];
printf("\n\t请输入存储文件名：");
scanf("%s",filename);//输入将要储存的文件名
fp=fopen(filename,"w");
for(i=1;i<=L->length;i++)//将链表中数据逐一写入文件中
{
fprintf(fp,"%d (%d)\n",L->r[i].key,L->r[i].num);
}
fclose(fp);
}

void Print(qSqList L)//打印数据个数以及排序过程中的比较次数和移动次数
{
printf("\n\t数据个数:%ld",L->length);
printf("\n\t比较次数:%ld",comparetimes);
printf("\n\t移动次数:%ld",shifttimes);
}

struct node Min1(struct node a,struct node b)//比较两接点关键字的大小
{
struct node temp;
if(a.key>b.key)
temp=b;
else
temp=a;
comparetimes++;
return(temp);
}

qSqList shellinsert(qSqList L,int dk)//对顺序表以dk为增量作直接插入排序
{
int i,j;
for(i=dk+1;i<=L->length;i++)
{
if(LT(L->r[i].key,L->r[i-dk].key))//将L->r[i]插入到有序增量子表
{
L->r[0]=L->r[i];//将L->r[i]暂时存储在L->r[0]
shifttimes++;
for(j=i-dk;j>0&<(L->r[0].key,L->r[j].key);j-=dk)//记录后移，查找插入位置
{
L->r[j+dk]=L->r[j];
comparetimes++;
shifttimes++;
}
if(j>0)
comparetimes++;
L->r[j+dk]=L->r[0];//插入
shifttimes++;
}
comparetimes++;
}
// Print(L);
return(L);
}

qSqList shell(qSqList L)//希尔排序
{
int i,t=0;
int k;
for(t=0;LQ(pow(2,t),(L->length+1));t++);
t=t-1;
// printf("%d",t);
for(i=1;i<=t;++i)
{
k=(int)pow(2,t-i+1)-1;//计算排序增量
L=shellinsert(L,k);
}
Print(L);
Print2(L);
return(L);
}

long Quicksort(qSqList L,long low,long high)//交换顺序表L中子表L->r[low..high]的记录，使枢轴记录到位，并返回其所在位置
{
int pivotkey;
pivotkey=L->r[low].key;//用序列的第一个记录作枢轴记录
while(low<high)//从表的两端交替地向中间扫描
{
while(low<high&&L->r[high].key>=pivotkey)//将比枢轴记录小的记录交换到低端
{
comparetimes++;
high--;
}
comparetimes++;
L->r[0]=L->r[low];
shifttimes++;
L->r[low]=L->r[high];
shifttimes++;
L->r[high]=L->r[0];
shifttimes++;
while(low<high&&L->r[low].key<=pivotkey)//将比枢轴记录大的记录交换到高端
{
comparetimes++;
low++;
}
comparetimes++;
L->r[0]=L->r[low];
shifttimes++;
L->r[low]=L->r[high];
shifttimes++;
L->r[high]=L->r[0];
shifttimes++;
}
return(low);//返回枢轴所在位置
}

qSqList Quick2(qSqList L,long low,long high)//对顺序表L中的子序列L.r[low..high]作快速排序
{
long pivot;
if(low<high)//序列长度大于1
{
pivot=Quicksort(L,low,high);//将序列一分为二
Quick2(L,low,pivot-1);//对低位子表递归排序
Quick2(L,pivot+1,high);//对高位子表递归排序
}
return(L);
}

qSqList Quick(qSqList L)//对顺序表作快速排序
{
long low,high;
low=1;//将第一个数据所在位置定义为低位
high=L->length;//将最后一个数据所在位置定义为高位
L=Quick2(L,low,high);//对顺序表作快速排序
Print(L);
Print2(L);
return(L);
}

void TourSort(SqList *L,long n)//锦标赛排序
{
qSqList Lp;
long i=0,t=1,k=1,w;
while(t<n)//t表示完全二叉树的结点个数
{
t=(long)pow(2,i);
i++;
}
t=2*t;
Lp=(qSqList)malloc((sizeof(SqList)));
Lp->length=t-1;
for(i=t-1;i>=t/2;i--)
{
if(k>n)
Lp->r[i].key=MAXNUM;
else
{
Lp->r[i]=L->r[k];

}
shifttimes++;
k++;
}
i=t-1;
while(i!=1)
{
Lp->r[i/2]=Min1(Lp->r[i],Lp->r[i-1]);
i-=2;
comparetimes++;
shifttimes++;
}
for(i=1;i<=n;i++)
{
L->r[i]=Lp->r[1];
shifttimes++;
w=1;
while(w<t/2)
{
if(Lp->r[2*w].key==Lp->r[w].key)
w*=2;
else
w=2*w+1;
}
Lp->r[w].key=MAXNUM;//将其赋为最大值
shifttimes++;
if(w%2)
Lp->r[w/2]=Lp->r[w-1];
else
Lp->r[w/2]=Lp->r[w+1];
shifttimes++;
while(w!=1)
{
if(w%2)
Lp->r[w/2]=Min1(Lp->r[w],Lp->r[w-1]);
else
Lp->r[w/2]=Min1(Lp->r[w],Lp->r[w+1]);
comparetimes++;
shifttimes++;
w/=2;
}
}
Print(L);
Print2(L);
}

void Heapadjust(qSqList L,long s,long m)//调整L->[s]的关键字，使L->r[s..m]成为一个大顶堆
{
long j;
struct node rc;
rc=L->r[s];
for(j=2*s;j<=m;j*=2)//沿key较大的接点向下筛选
{
if(j<m&<(L->r[j].key,L->r[j+1].key))//j为key较大的记录的下标
{
j++;
comparetimes++;
}
if(!LT(rc.key,L->r[j].key))
{
comparetimes++;
break;
}
L->r[s]=L->r[j];//rc插入位置s
shifttimes++;
s=j;
}
L->r[s]=rc;//插入
shifttimes++;
}

qSqList Heap(qSqList L)//堆排序
{
long i;
for(i=L->length/2;i>0;--i)//把L建成大顶堆
Heapadjust(L,i,L->length);
for(i=L->length;i>1;--i)//将堆顶记录和当前未经排序子序列中最后一个记录交换
{
L->r[0]=L->r[1];
L->r[1]=L->r[i];
L->r[i]=L->r[0];
shifttimes=shifttimes+3;
Heapadjust(L,1,i-1);//将L重新调整为大顶堆
}
Print(L);
Print2(L);
return(L);
}

void Merge(qSqList L,int low,int m,int high)//将两个有序表R[low..m]he R[m+1..high]归并为一个有序表R[low,high]
{
int i=low,j=m+1,k=0;//k是temp的下标，i,j分别为第1，2段的下标
struct node *temp;
temp=(struct node*)malloc((high-low+1)*sizeof(struct node));//用于临时保存有序序列
while(i<=m&&j<=high)//在第1段和第2段均未扫描完时循环
{
if(LT(L->r[j].key,L->r[i].key))//将第1段中的记录放入temp中
{
temp[k]=L->r[j];
j++;
k++;
}
else//将第2段中的记录放入temp中
{
temp[k]=L->r[i];
k++;
i++;
}
}
while(i<=m)//将第1段余下的部分复制到temp
{
temp[k]=L->r[i];
k++;
i++;
}
while(j<=high)//将第2段余下的部分复制到temp
{
temp[k]=L->r[j];
k++;
j++;
}
for(k=0,i=low;i<=high;i++,k++)//将temp复制回L中
{
L->r[i]=temp[k];
}
}

void MSort(qSqList L,int low,int high)//二路归并排序
{
int m;
if (low<high)
{
m=(low+high)/2;
MSort(L,low,m);
MSort(L,m+1,high);
Merge(L,low,m,high);
}
}

void Merging(qSqList L)//归并排序
{
MSort(L,1,L->length);
Print2(L);
}

void Radixsort(qSqList L)//基数排序
{
int g,i,j,k,d=2;
struct node2 *p,*s,*t,*head[10],*tail[10];//定义各链队的首尾指针
for(i=1;i<=L->length;i++) //建立链表
{
s = (struct node2*)malloc(sizeof(struct node2));
s->r.key = L->r[i].key;
s->r.num= L->r[i].num;
if(i==1)
{
t = s;
p = s;
g++;}
else
{
t->next = s;
t = s;
g++;
}
t->next = NULL;
}
d=1;
for(i=1;i<6;i++)
{
for(j=0;j<10;j++)
{head[j] = tail[j] = NULL;} //初始化各链队首、尾指针
while(p!=NULL)//对于原链表中的每个结点循环
{
k = p->r.key/d;
k = k%10;
if(head[k]==NULL)//进行分配
{
head[k]=p;
tail[k]=p;
}
else
{
tail[k]->next=p;
tail[k]=p;
}
p = p->next;//取下一个待排序的元素
}
p=NULL;
for(j=0;j<10;j++)//对每一个链队循环
{
if(head[j]!=NULL)//进行搜集
{
if(p == NULL)
{
p = head[j];
t = tail[j];
}
else
{
t->next=head[j];
t = tail[j];
}
}
}
t->next=NULL;//最后一个结点的next置为空
d=d*10;
}
i=1;
while(p!=NULL)
{
L->r[i] = p->r;
i++;
p=p->next;}
Print2(L);
}

char chmenu()//对排序方法进行选择
{
char ch;
printf("\n\t请选择排序方法:"
"\n\t*************"
"\n\t1.Shell排序"
"\n\t2.Quick排序"
"\n\t3.锦标赛排序"
"\n\t4.堆排序"
"\n\t5.归并排序"
"\n\t6.基排序"
"\n\t7.结束"
"\n\t*************");
do{
printf("\n\tplease choose (1-7):");
getchar();
ch=getchar();
}while(!(ch>'0'&&ch<'8'));
return(ch);
}

void main()
{
int a=1;
FILE *fp;
char ch,filename[N];
qSqList L;
while(a)
{
printf("\n\t请输入读入文件名:");//输入要读入的文件名
scanf("%s",filename);
if((fp=fopen(filename,"r"))==NULL)
{
printf("cannot open the file\n");
exit(0);
}
L=creat(filename);
while(1)
{
if((ch=chmenu())=='7')
break;
switch(ch)
{
case'1':{shifttimes=comparetimes=0;shell(L);}break;
case'2':{shifttimes=comparetimes=0;Quick(L);}break;
case'3':{shifttimes=comparetimes=0;TourSort(L,L->length);}break;
case'4':{shifttimes=comparetimes=0;Heap(L);}break;
case'5':{shifttimes=comparetimes=0;Merging(L);}break;
case'6':{shifttimes=comparetimes=0;Radixsort(L);}break;
}
}
printf("\n\t***************"
"\n\t1.继续读入文件"
"\n\t0.结束"
"\n\t***************");
do{
printf("\n\tplease choose (0-1):");
getchar();
scanf("%d",&a);
}while(!(a==1||a==0));

}
}

Ⅳ 排序算法有哪些

1.插入排序—直接插入排序(Straight
Insertion
Sort)
2.
插入排序—希尔排序（Shell`s
Sort）
3.
选择排序—简单选择排序（Simple
Selection
Sort）
4.
选择排序—堆排序（Heap
Sort）
5.
交换排序—冒泡排序（Bubble
Sort）
6.
交换排序—快速排序（Quick
Sort）
7.
归并排序（Merge
Sort）
8.
桶排序/基数排序(Radix
Sort)

Ⅵ 排序算法有多少种

排序(Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。
排序就是把集合中的元素按照一定的次序排序在一起。一般来说有升序排列和降序排列2种排序，在算法中有8中基本排序：
(1)冒泡排序；
(2)选择排序；
(3)插入排序；
(4)希尔排序；
(5)归并排序；
(6)快速排序；
(7)基数排序；
(8)堆排序；
(9)计数排序；
(10)桶排序。
插入排序
插入排序算法是基于某序列已经有序排列的情况下，通过一次插入一个元素的方式按照原有排序方式增加元素。这种比较是从该有序序列的最末端开始执行，即要插入序列中的元素最先和有序序列中最大的元素比较，若其大于该最大元素，则可直接插入最大元素的后面即可，否则再向前一位比较查找直至找到应该插入的位置为止。插入排序的基本思想是，每次将1个待排序的记录按其关键字大小插入到前面已经排好序的子序列中，寻找最适当的位置，直至全部记录插入完毕。执行过程中，若遇到和插入元素相等的位置，则将要插人的元素放在该相等元素的后面，因此插入该元素后并未改变原序列的前后顺序。我们认为插入排序也是一种稳定的排序方法。插入排序分直接插入排序、折半插入排序和希尔排序3类。
冒泡排序
冒泡排序算法是把较小的元素往前调或者把较大的元素往后调。这种方法主要是通过对相邻两个元素进行大小的比较，根据比较结果和算法规则对该二元素的位置进行交换，这样逐个依次进行比较和交换，就能达到排序目的。冒泡排序的基本思想是，首先将第1个和第2个记录的关键字比较大小，如果是逆序的，就将这两个记录进行交换，再对第2个和第3个记录的关键字进行比较，依次类推，重复进行上述计算，直至完成第(n一1)个和第n个记录的关键字之间的比较，此后，再按照上述过程进行第2次、第3次排序，直至整个序列有序为止。排序过程中要特别注意的是，当相邻两个元素大小一致时，这一步操作就不需要交换位置，因此也说明冒泡排序是一种严格的稳定排序算法，它不改变序列中相同元素之间的相对位置关系。
选择排序
选择排序算法的基本思路是为每一个位置选择当前最小的元素。选择排序的基本思想是，基于直接选择排序和堆排序这两种基本的简单排序方法。首先从第1个位置开始对全部元素进行选择，选出全部元素中最小的给该位置，再对第2个位置进行选择，在剩余元素中选择最小的给该位置即可；以此类推，重复进行“最小元素”的选择，直至完成第(n-1)个位置的元素选择，则第n个位置就只剩唯一的最大元素，此时不需再进行选择。使用这种排序时，要注意其中一个不同于冒泡法的细节。举例说明：序列58539．我们知道第一遍选择第1个元素“5”会和元素“3”交换，那么原序列中的两个相同元素“5”之间的前后相对顺序就发生了改变。因此，我们说选择排序不是稳定的排序算法，它在计算过程中会破坏稳定性。
快速排序
快速排序的基本思想是:通过一趟排序算法把所需要排序的序列的元素分割成两大块，其中，一部分的元素都要小于或等于另外一部分的序列元素，然后仍根据该种方法对划分后的这两块序列的元素分别再次实行快速排序算法，排序实现的整个过程可以是递归的来进行调用，最终能够实现将所需排序的无序序列元素变为一个有序的序列。
归并排序
归并排序算法就是把序列递归划分成为一个个短序列，以其中只有1个元素的直接序列或者只有2个元素的序列作为短序列的递归出口，再将全部有序的短序列按照一定的规则进行排序为长序列。归并排序融合了分治策略，即将含有n个记录的初始序列中的每个记录均视为长度为1的子序列，再将这n个子序列两两合并得到n/2个长度为2(当凡为奇数时会出现长度为l的情况)的有序子序列；将上述步骤重复操作，直至得到1个长度为n的有序长序列。需要注意的是，在进行元素比较和交换时，若两个元素大小相等则不必刻意交换位置，因此该算法不会破坏序列的稳定性，即归并排序也是稳定的排序算法。

Ⅶ Swift - 常用的排序算法

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序详解

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

选择排序详解

插入排序（Insertion-Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

详解插入排序

1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

希尔排序的提出，主要基于以下两点：

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

希尔排序详情

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

归并排序详解

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

快速排序详解

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆排序详解

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

计数排序详解

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，需要做到这两点：

桶排序详解

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

基数排序详解

Ⅷ 几种常见的排序算法

for(i = 0; i < n; i++) for(j = 0; j < n - 1 - i; j++){if(arr[j] arr[j + 1]){arr[j] = arr[j] ^ arr[j+1]; arr[j+1] = arr[j] ^ arr[j+1]; arr[j] = arr[j] ^ arr[j+1];}}} 交换两个数据，可以用用临时变量，也可用以下的两个方法a = a^b;b = a^b;a = a^b;或者 a = a + b;b = a - b;a = a - b;// 选择排序 void SelectSort(int arr[], int n){int i, j;int min; for(i = 0; i < n - 1; i++){int index = 0; min = arr[i]; for(j = i + 1; j < n; j++) //找出 i+1 - n 无序区的最小者与arr[i]交换{if(arr[j] < min){min = arr[j];index = j;}}if(index != 0) //表明无序区有比arr[i]小的元素{arr[i] = arr[i]^arr[index]; arr[index] = arr[i]^arr[index]; arr[i] = arr[i]^arr[index];}}}感觉比冒泡法好多啦 //快速排序算法

Ⅸ 排序算法是怎样的

一、背景介绍

在计算机科学与数学中，排序算法（Sorting algorithm）是一种能将一串资料依照特定排序方式进行排列的一种算法。

最常用到的排序方式是数字顺序以及字典顺序。

有效的排序算法在一些算法（例如搜寻算法与合并算法）中是重要的， 如此这些算法才能得到正确解答。

排序算法也用在处理文字资料以及产生人类可读的输出结果。

基本上，排序算法的输出必须遵守下列两个原则：

1、输出结果为递增序列（递增是针对所需的排序顺序而言）；

2、输出结果是原输入的一种排列、或是重组；

虽然排序算法是一个简单的问题，但是从计算机科学发展以来，在此问题上已经有大量的研究。 更多的新算法仍在不断的被发明。

二、知识剖析

查找和排序算法是算法的入门知识，其经典思想可以用于很多算法当中。因为其实现代码较短，应用较常见。 所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗，只要熟悉了思想，灵活运用也不是难事。

一般在面试中最常考的是快速排序和冒泡排序，并且经常有面试官要求现场写出这两种排序的代码。对这两种排序的代码一定要信手拈来才行。除此之外，还有插入排序、冒泡排序、堆排序、基数排序、桶排序等。

三、常见的几种算法：

冒泡算法、选择排序、插入排序、希尔排序、归并排序、快速排序

算法的特点：

1、有限性：一个算法必须保证执行有限步之后结束。

2、确切性： 一个算法的每一步骤必须有确切的定义。

3、输入：一个算法有零个或多个输入，以刻画运算对象的初始情况，所谓零个输入是指算法本身给定了初始条件。

4、输出：一个算法有一个或多个输出。没有输出的算法毫无意义。

5、可行性：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。

Ⅹ 几种排序算法的比较

一、八大排序算法的总体比较

4.3、堆的插入：

每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列，然后将这个新数据插入到这个有序数据中

（1）用大根堆排序的基本思想

先将初始数组建成一个大根堆，此对为初始的无序区；

再将最大的元素和无序区的最后一个记录交换，由此得到新的无序区和有序区，且满足<=的值；

由于交换后新的根可能违反堆性质，故将当前无序区调整为堆。然后再次将其中最大的元素和该区间的最后一个记录交换，由此得到新的无序区和有序区，且仍满足关系的值<=的值，同样要将其调整为堆；

..........

直到无序区只有一个元素为止；

4.4：应用

寻找M个数中的前K个最小的数并保持有序；

时间复杂度：O(K)[创建K个元素最大堆的时间复杂度] +（M-K）*log(K)[对剩余M-K个数据进行比较并每次对最大堆进行从新最大堆化]

5.希尔排序

（1）基本思想

先将整个待排序元素序列分割成若干子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序（因为直接插入排序在元素基本有序的情况下，效率很高）；

（2）适用场景

比较在希尔排序中是最主要的操作，而不是交换。用已知最好的步长序列的希尔排序比直接插入排序要快，甚至在小数组中比快速排序和堆排序还快，但在涉及大量数据时希尔排序还是不如快排；

6.归并排序

（1）基本思想

首先将初始序列的n个记录看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2的有序子序列，在此基础上，再对长度为2的有序子序列进行两两归并，得到若干个长度为4的有序子序列，以此类推，直到得到一个长度为n的有序序列为止；

（2）适用场景

若n较大，并且要求排序稳定，则可以选择归并排序；

7.简单选择排序

（1）基本思想

第一趟：从第一个记录开始，将后面n-1个记录进行比较，找到其中最小的记录和第一个记录进行交换；

第二趟：从第二个记录开始，将后面n-2个记录进行比较，找到其中最小的记录和第2个记录进行交换；

...........

第i趟：从第i个记录开始，将后面n-i个记录进行比较，找到其中最小的记录和第i个记录进行交换；

以此类推，经过n-1趟比较，将n-1个记录排到位，剩下一个最大记录直接排在最后；