1. 求数据结构题
就行了，准过！
第一章：绪论
1.1：数据结构课程的任务是：讨论数据的各种逻辑结构、在计算机中的存储结构以及各种操作的算法设计。
1.2：数据：是客观描述事物的数字、字符以及所有的能输入到计算机中并能被计算机接收的各种集合的统称。
数据元素：表示一个事物的一组数据称作是一个数据元素，是数据的基本单位。
数据项：是数据元素中有独立含义的、不可分割的最小标识单位。
数据结构概念包含三个方面：数据的逻辑结构、数据的存储结构的数据的操作。
1.3数据的逻辑结构指数据元素之间的逻辑关系，用一个数据元素的集合定义在此集合上的若干关系来表示，数据结构可以分为三种：线性结构、树结构和图。
1.4：数据元素及其关系在计算机中的存储表示称为数据的存储结构，也称为物理结构。
数据的存储结构基本形式有两种：顺序存储结构和链式存储结构。
2.1：算法：一个算法是一个有穷规则的集合，其规则确定一个解决某一特定类型问题的操作序列。算法规则需满足以下五个特性：
输入——算法有零个或多个输入数据。
输出——算法有一个或多个输出数据，与输入数据有某种特定关系。
有穷性——算法必须在执行又穷步之后结束。
确定性——算法的每个步骤必须含义明确，无二义性。
可行性——算法的每步操作必须是基本的，它们的原则上都能够精确地进行，用笔和纸做有穷次就可以完成。
有穷性和可行性是算法最重要的两个特征。
2.2：算法与数据结构：算法建立数据结构之上，对数据结构的操作需用算法来描述。
算法设计依赖数据的逻辑结构，算法实现依赖数据结构的存储结构。
2.3：算法的设计应满足五个目标：
正确性：算法应确切的满足应用问题的需求，这是算法设计的基本目标。
健壮性：即使输入数据不合适，算法也能做出适当的处理，不会导致不可控结
高时间效率：算法的执行时间越短，时间效率越高。 果。
高空间效率：算法执行时占用的存储空间越少，空间效率越高。
可读性：算法的可读性有利于人们对算法的理解。
2.4：度量算法的时间效率，时间复杂度，（课本39页）。
2.5：递归定义：即用一个概念本身直接或间接地定义它自己。递归定义有两个条件：
至少有一条初始定义是非递归的，如1！=1.
由已知函数值逐步递推计算出未知函数值，如用（n-1）！定义n！。
第二章：线性表
1.1线性表：线性表是由n(n>=0)个类型相同的数据元素a0,a1,a2,…an-1,组成的有限序列,记作： LinearList = (a0,a1,a2,…an-1)
其中，元素ai可以是整数、浮点数、字符、也可以是对象。n是线性表的元素个数，成为线性表长度。若n=0，则LinearList为空表。若n>0，则a0没有前驱元素，an-1没有后继元素，ai（0<i<n-1）有且仅有一个直接前驱元素ai-1和一个直接后继元素ai+1。
1.2线性表的顺序存储是用一组连续的内存单元依次存放线性表的数据元素，元素在内存的物理存储次序与它们在线性表中的逻辑次序相同。
线性表的数据元素数据同一种数据类型，设每个元素占用c字节，a0的存储地址为
Loc（a0），则ai的存储地址Loc（ai）为：Loc（ai） = Loc（a0）+ i*c
数组是顺序存储的随机存储结构，它占用一组连续的存储单元，通过下标识别元素，元素地址是下标的线性函数。
1.3：顺序表的插入和删除操作要移动数据元素。平均移动次数是 属数据表长度的一半。（课本第50页）
1.4：线性表的链式存储是用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻，必须采用附加信息表示数据元素之间的顺序关系。
它有两个域组成：数据域和地址域。通常成为节点。（课本第55页及56页）
1.5单链表（课本56页）
单链表的遍历：Node<E> p = head; while(p!=null)
单链表的插入和删除操作非常简便，只要改变节点间的链接关系，不需移动数据元素。
单链表的插入操作：1）：空表插入/头插入 2)中间插入/尾插入
if(head == null) Node<E> q = new Node<E>(x);
{ head = new Node<E>(x); q.next = p.next;
}else{ p.next = q;
Node<E> q=new Node<E>(x); 中间插入或尾插入都不会改变单表
q.next = head; 的头指针head。
head = q;
}
单链表的删除操作：
头删除：head = head.next;
中间/尾删除：if(p.next!=null)
循环单链表：如果单链表最后一个节点的next链保存单链表的头指针head值，则该单链表成为环形结构，称为循环单链表。（课本67）
若rear是单链表的尾指针，则执行（rear.next=head;）语句，使单链表成为一条循环单链表。当head.next==head时，循环单链表为空。
1.6：双链表结构：双链表的每个结点有两个链域，分别指向它的前驱和后继结点，
当head.next==null时，双链表为空。
设p指向双链表中非两端的某个结点，则成立下列关系：p=p.next.prev=p.prev.next。
双链表的插入和删除：1）插入 2)删除
q=new DLinkNode（x）； p.prev.next = p.next;
q.prev=p.prev;q.next =p; if(p.next=null){
p.prev.next = q;p.prev=q; (p.next).prev = p.prev;}
循环双链表：当head.next==head且head.prev==head时，循环双链表为空。
第三章：栈和队列
1.1栈：栈是一种特殊的线性表，其中插入和删除操作只允许在线性表的一端进行。允许操作的一端称为栈顶，不允许操作的一端称为栈底。栈有顺序栈和链式栈。
栈中插入元素的操作称为入栈，删除元素的操作称为出栈。没有元素的中称为空栈。
栈的进出栈顺序：后进先出，先进后出。（及75页的思考题）。
1.2：队列：队列是一种特殊的线性表，其中插入和删除操作分别在线性表的两端进行。
向队列中插入元素的过程称为入队，删除元素的过程称为出对，允许入队的一端称为队尾，允许出队的一端称为对头。没有元素的队列称为空队列。队列是先进先出。
第四章：串
1.1：串是一种特殊的线性表，其特殊性在于线性表中的每个元素是一个字符。一个串记为： s=“s0s1s2…sn-1” 其中n>=0,s是串名，一对双引号括起来的字符序列s0s1s2…sn-1是串值，si（i=0，1，2，…n-1）为特定字符集合中的一个字符。一个串中包含的字符个数称为串的长度。
长度为0的串称为空串，记作“”，而由一个或多个空格字符构成的字符串称为空格串。
子串：由串s中任意连续字符组成的一个子序列sub称为s的子串，s称为sub的主串。子串的序号是指该子串的第一个字符在主串中的序号。
串比较：两个串可比较是否相等，也可比较大小。两个串（子串）相等的充要条件是两个串（子串）的长度相同，并且各对应位置上的字符也相同。
两个串的大小由对应位置的第一个不同字符的大小决定，字符比较次序是从头开始依次向后。当两个串长度不等而对应位置的字符都相同时，较长的串定义为较“大”。
第五章：数组和广义表
1.1：数组是一种数据结构，数据元素具有相同的数据类型。一维数组的逻辑结构是线性表，多维数组是线性表的扩展。
1.2：一维数组：一维数组采用顺序存储结构。一个一维数组占用一组连续的存储单元。
设数组第一个元素a0的存储地址为Loc（a0），每个元素占用c字节，则数组其他元素ai的存储地址Loc（ai）为： Loc（ai）= Loc（a0）+i*c
数组通过下标识别元素，元素地址是下标的线性函数。一个下标能够唯一确定一个元素，所划给的时间是O（1）。因此数组是随机存取结构，这是数组最大的优点。
1.3：多维数组的遍历：有两种次序：行主序和列主序。
行主序：以行为主序，按行递增访问数组元素，访问完第i行的所有元素之后再访问第i+1行的元素，同一行上按列递增访问数组元素。
a00,a01,…a0(n-1), a10,a11,…a1(n-1),…a(m-1)0,a(m-1)1,…,a(m-1)(n-1)
2)列主序：以列为主序，按列递增访问数组元素，访问完第j列的所有元素之后再访问第j+1列的元素，同一列上按列递增访问数组元素。
多维数组的存储结构：多维数组也是由多个一维数组组合而成，组合方式有一下两种。
静态多维数组的顺序存储结构：可按行主序和列主序进行顺序存储。
按行主序存储时，元素aij的地址为：Loc（aij）= Loc（a00）+（i*n+j）*c
按列主序存储时，Loc（aij）= Loc（a00）+（j*m+i）*c
动态多维数组的存储结构。
二维数组元素地址就是两个下标的线性函数。无论采用哪种存储结构，多维数组都是基于一维数组的，因此也只能进行赋值、取值两种存取操作，不能进行插入，删除操作。
第六章：
树是数据元素（结点）之间具有层次关系的非线性结构。在树结构中，除根以外的结点只有一个直接前驱结点，可以有零至多个直接后继结点。根没有前驱结点。
树是由n（n>=0）个结点组成的有限集合（树中元素通常称为结点）。N=0的树称为空树；n>0大的树T；
@有一个特殊的结点称为根结点，它只有后继结点，没有前驱结点。
@除根结点之外的其他结点分为m（m>=0）个互不相交的集合T0,T1,T3……..,Tm-1，其中每个集合Ti（0<=i<m）本身又是一棵树，称为根的子树。
树是递归定义的。结点是树大的基本单位，若干个结点组成一棵子树，若干棵互不相交的子树组成一棵树。树的每个结点都是该树中某一棵子树的根。因此，树是由结点组成的、结点之间具有层次关系大的非线性结构。
结点的前驱结点称为其父母结点，反之，结点大的后继结点称为其孩子结点。一棵树中，只有根结点没有父母结点，其他结点有且仅有一个父母结点。
拥有同一个父母结点的多个结点之间称为兄弟结点。结点的祖先是指从根结点到其父母结点所经过大的所有结点。结点的后代是指该结点的所有孩子结点，以及孩子的孩子等。
结点的度是结点所拥有子树的棵数。度为0的结点称为叶子结点，又叫终端结点；树中除叶子结点之外的其他结点称为分支结点，又叫非叶子结点或非终端结点。树的度是指树中各结点度的最大值。
结点的层次属性反应结点处于树中的层次位置。约定根结点的层次为1，其他结点的层次是其父母结点的层次加1。显然，兄弟结点的层次相同。
树的高度或深度是树中结点的最大层次树。
设树中x结点是y结点的父母结点，有序对（x，y）称为连接这两个结点的分支，也称为边。
设（X0,X1,….,Xk-1）是由树中结点组成的一个序列，且（Xi，Xi+1）（0<=i<k-1）都是树中的边，则该序列称为从X0到Xk-1的一条路径。路径长度为路径上的边数。
在树的定义中，结点的子树T0，T1…..,Tm-1之间没有次序，可以交换位置，称为无序树，简称树。如果结点的子树T0,T1……,Tm-1从左到右是有次序的，不能交换位置，则 称该树为有序树。
森林是m（m>=0）棵互不相干的树的集合。给森林加上一个根结点就变成一棵树，将树的根节点删除就变成森林。
二叉树的性质1：若根结点的层次为1，则二叉树第i层最多有2 的i-1次方（i>=1）个结点。
二叉树的性质2：在高度为k的二叉树中，最多有2的k次方减一个结点。
二叉树的性质3：设一棵二叉树的叶子结点数为n0,2度结点数为n2，则n0=n2+1。
一棵高度为k的满二叉树是具有2的k次方减一个结点的二叉树。满二叉树中每一层的结点数目都达到最大值。对满二叉树的结点进行连续编号，约定根节点的序号为0，从根节点开始，自上而下，每层自左至右编号。
一棵具有n个结点高度为k的二叉树，如果他的每个节点都与高度为k的满二叉树中序号为0~n-1
的结点一一对应，则这棵二叉树为为完全二叉树。
满二叉树是完全二叉树，而完全二叉树不一定是满二叉树。完全二叉树的第1~k-1层是满二叉树第k层不满，并且该层所有结点必须集中在该层左边的若干位置上。
二叉树的性质4：一棵具有n个结点的完全二叉树，其高度k=log2n的绝对值+1
二叉树的性质5：一棵具有n个结点的完全二叉树，对序号为i的结点，有
@若i=0，则i为根节点，无父母结点；若i>0，则i的父母结点的序号为[（i-1）/2]。
@若2i+1<n，则i的左孩子结点序号为2i+1；否则i无左孩子。
@若2i+2<n，则i的右孩子结点的序号为2i+2，否则i无右孩子。
二叉树的遍历
二叉树的遍历是按照一定规则和次序访问二叉树中的所有结点，并且每个结点仅被访问一次。
二叉树的三种次序遍历
1：先根次序；访问根节点，遍历左子树，遍历右子树。
2：中根次序；遍历左子树，访问右子树，遍历右子树。
3：后根次序；遍历左子树，遍历右子树，访问根节点。
先根次序遍历时，最先访问根节点；后根次序遍历时，最后访问根节点；中根次序遍历时，左子树上的结点在根节点之前访问，右子树上的结点在根节点之后访问。
二叉树的插入和删除操作P147
二叉树的层次遍历P149
习题P167 6—10，6—19
第七章
图是由定点集合及顶点间的关系集合组成的一种数据关边系。顶点之间的关系成为边。一个图G记为G=（V,E），V是顶点A的有限集合，E是边的有限集合。即 V=
E=或E=其中Path（A,B）表示从顶点A到B的一条单向通路，即Path（A,B）是有方向的。
无向图中的边事没有方向，每条边用两个顶点的无序对表示。
有向图中的边是有方向，每条边用两个顶点的有序对表示。
完全图指图的边数达到最大值。n个顶点的完全图记为Kn。无向完全图Kn的边数为n*（n-1）/2,有向完全图Kn的边数为n*（n-1）。
子图：设图G==(V,E),G’=(V’,E’)，若V’包含于V且E’包含于E,则称图G’是G的子图。若G’是G的真子图。
连通图：在无向图G中，若从顶点VI到Vj有路径，则称Vi和Vj是联通的。若图G中任意一对顶点Vi和Vj（Vi不等于Vj）都是联通的，则称G为连通图。非连通图的极大联通子图称为该图的联通分量。
强连通图：在有向图中，若在每一对顶点Vi和Vj（Vi不等于Vj）之间都存在一条从Vi到Vj的路径，也存在一条从Vi到Vj的路径，也存在一条从Vi到Vj的路径，则称该图的强连通图。非强连通图的极大强连通子图称为该图的强连通图分量。
图的遍历
遍历图是指从图G中任意一个顶点V出发，沿着图中的边前行，到达并访问图中的所有顶点，且每个顶点仅被访问一次。遍历图要考虑一下三个问题：
@指定遍历的第一个访问顶点
@由于一个顶点可能与多个顶点相邻，因此要在多个邻接顶点之间约定一种访问次序。
@由于图中可能存在回路，在访问某个顶点之后，可能沿着某条路径又回到该顶点。
深度优先搜索
图的深度优先搜索策略是，访问某个顶点v，接着寻找v的另一个未被访问的邻接顶点w访问，如此反复执行，走过一条较长路径到达最远顶点；若顶点v没有未被访问的其他邻接顶点，则回到前一个被访问顶点，再寻找其他访问路径。
图的深度优先搜索遍历算法P188
联通的无回路的无向图，简称树。树中的悬挂点又成为树叶，其他顶点称为分支点。各连通分量均为树的图称为森林，树是森林。
由于树中无回路，因此树中必定无自身环也无重边（否则他有回路）若去掉树中的任意一条边，则变成森林，成为非联通图；若给树加上一条边，形成图中的一条回路，则不是树。P191
生成树和生成森林：
一个连通无向图的生成树是该图的一个极小联通生成子图，它包含原图中所有顶点（n个）以及足以构成一棵树的n-1条边。
一个非联通的无向图，其各连通图分量的生成图组成该图的生成森林。
图的生成图或生成森林不是唯一的，从不同顶点开始、采用不同遍历可以得到不同的生成树或森林。
在生成树中，任何树中，任何两个顶点之间只有唯一的一条路径。
第八章
折半查找算法描述 P206,P207
二叉排序树及其查找：
二叉排序树或者是一棵空树；或者是具有下列性质的二叉树：
@每个结点都有一个作为查找依据的关键字，所有结点的关键字互不相同。
@若一个结点的左子树不空，则左子树上所有结点的关键字均小于这个节点的关键字；
@每个结点的左右子树也分别为二叉排序树。
在一棵二叉排序树中，查找值为value的结点，算法描述如下：
@从根结点开始，设p指向根结点
@将value与p结点的关键字进行比较，若两者相等，则查找成功；若value值较小，则在p的左子树中继续查找；若value值较大，则在p的右子树中继续查找。
@重复执行上一步，直到查找成功或p为空，若p为空，则查找不成功。
习题 8-6
第九章
直接插入排序算法描述：p228
冒泡排序算法的描述：p232
快速排序算法描述p233
直接选择排序算法描述p236
直接选择排序算法实现如下：
Public static void selectSort(int[]table){
for(int i=0;i<table.length-1;i++){
int min=I;
for(int j=i+1;j<table.length;j++){
if(table[j]<table[min])
min=j;
if(min!=i){
int temp=table[i];
table[i]==table[min];
table[min]=temp;
}
}
}
}
堆排序是完全二叉树的应用，是充分利用完全二叉树特性的一种选择排序。
堆定义：设n个元素的数据序列，当且仅当满足下列关系
k1<=k2i+1且ki<=k2i+2 i=0,1,2,3,….,[n/2-1]
或ki>==k2i+1且ki>=2i+2i=0,1,2,3,…..[n/2-1]时，序列称为最小堆或最大堆。将最小（大）堆看成是一颗完全二叉树的层次遍历序列，则任意一个结点的关键字都小于等于（大于等于）它的孩子节点的关键字值，由此可知，根结点值最小（大）。根据二叉树的性质5，完全二叉树中的第i（0<=i<n）个结点，如果有孩子，则左孩子为第2i+1个结点，右孩子为第2i+2个结点。
希望对你会有所帮助。
2. 1、设计一个用带头结点的单链表表示的直接插入排序算法，各结点结构如图：
首先，你没有想清楚你就开始写程序了，其次，你的写程序的习惯不好。下班回来看了下你的程序，为了节省时间，我在你的程序稍加改动，并只改了从高到低的情况，现将问题描述如下，在程序中也会注释出来：1、可能是因为我的系统是日文的，你程序上的解释就出现了问题，请注意检查。2、cur指代不明。3、结束条件判断错误，有两处。下面在程序中详细说明，我是在你的程序上改的：#include<stdio.h>#include<stdlib.h>#define debug 1struct arry;void main() do if(temp->next->next==NULL)last=cur;/*这是说当新结点是最小的时候就直接插到尾结点后面，同时尾结点更新*/ } goto part2; /*下面一种情况就没有改，参照上面的错误自己改吧，我也没多少时间，呵呵*/ break; case 'd': case 'D': for (temp=head;temp->next!=NULL;temp=temp->next) } break; } part2: for (temp=head;t
3. 能不能帮我做一个常用排序算法的设计呢 跪求啊 帮帮忙吧 我对这个一窍不通啊
常用的排序有：
1.直接插入排序
2.希尔排序（最小增量排序）
3.简单选择排序
4.堆排序
5.冒泡排序
6.快速排序
7.归并排序
8.基数排序
4. 课程设计:采用单链表存储待排序的数据,实现直接插入排序算法.求算法
template<class T>
void LinkList<T>::InsertSort()
{
Node<T> * s=First->Next;
Node<T> * t=s->Next;
while(t!=NULL)
{
Node<T> * r=First;
while(s!=NULL)
{
if(t->Data<s->Data)
{
Node<T> * p=new Node<T>;
p->Data=t->Data;
p->Next=s;
r->Next=p;
s=NULL;
}
else if(t->Data==s->Data)
{
Node<T> * q=new Node<T>;
q->Data=t->Data;
q->Next=NULL;
r->Next=q;
s=NULL;
}
else
{
r=s;
s=s->Next;
}
}
Node<T> * h=t;
t=t->Next;
delete h;
s=First->Next;
}
}
5. 排序算法的实现与比较的课程设计
;
#include<stdio.h>
#define NUM 7 //宏定义
int i; //变量类型定义
typedef struct Node{
int data ; //数据域
struct Node *next; //指针域
}Node,*LNode; //用结构体构造结点及相应的指针
typedef struct Tree{
int data ;
struct Tree *left ;
struct Tree *right ;
}Tree,*LTree ; //用结构体构造树及相应的指针
CreateList( LNode Head ) //创建单链表
{
for(int i=1 ; i <=NUM ; i++) //创建循环，依次输入NUM个数据
{
LNode temp ; //中间结点
temp = (LNode) malloc( sizeof( Node ) ); //动态存储分配
temp-> next = NULL; //中间结点初始化
scanf("%2d",&temp-> data); //输入赋值到结点temp数据域
temp-> next = Head-> next ;
Head-> next = temp ; //将temp结点插入链表
}
return 1 ;//返回1
}
InsertSqTree( LTree &root , LNode temp ) //二叉树排序原则的设定
{
if(!root) //root为NULL时执行
{
root = (LTree)malloc(sizeof(Tree)); //动态存储分配
root-> left =NULL;
root-> right=NULL; //初始化
root-> data = temp-> data ; //赋值插入
return 1 ; //函数正常执行，返回1
}
else
{
if(root-> data>= temp-> data)
return InsertSqTree( root-> left , temp ) ; //比较插入左子树
else if(root-> data <temp-> data)
return InsertSqTree( root-> right , temp ); //比较插入右子树
}
return 1 ; //如果满足，就不做处理，返回1
}
void BianLiTree(LTree root) //采用中序遍历，实现将所有数字按从左向右递增的顺序排序
{
if(root) //root不为空执行
{BianLiTree(root-> left); //左递归处理至叶子结点，当root-> left为NULL时不执行
printf("%4d ",root-> data); //输出
BianLiTree(root-> right); //处理右结点
}
}
int main()
{
LNode Head = NULL;
LTree root = NULL ; //初始化
Head = (LNode) malloc(sizeof(Node)); //动态存储分配
Head-> next = NULL ; //初始化
printf("please input numbers:\n");//输入提示语句
if(!CreateList( Head )) //建单链表成功返回1不执行下一语句
return 0; //结束函数，返回0
LNode temp = Head-> next ; //将头指针的指针域赋值予中间结点
while( temp ) //temp为NULL时停止执行
{
if(!InsertSqTree( root ,temp )) //排序正常执行，返回1不执行下一语句
return 0 ; //结束函数，返回0
Head-> next = temp-> next ; //将中间指针的指针域赋值予头结点指针域
free(temp); //释放空间
temp = Head-> next ; //将头指针的指针域赋值予中间结点，以上三句实现了temp指针后移
}
printf("the result is:\n");//输出提示语句
BianLiTree(root); //采用中序遍历，输出并观察树结点
return 1; //函数正常结，返回1
}
6. python几种经典排序方法的实现
class SortMethod:
'''
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。
插入算法把要排序的数组分成两部分：
第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置）
第二部分就只包含这一个元素（即待插入元素）。
在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
'''
def insert_sort(lists):
# 插入排序
count = len(lists)
for i in range(1, count):
key = lists[i]
j = i - 1
while j >= 0:
if lists[j] > key:
lists[j + 1] = lists[j]
lists[j] = key
j -= 1
return lists
'''
希尔排序 (Shell Sort) 是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 DL．Shell 于 1959 年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。
'''
def shell_sort(lists):
# 希尔排序
count = len(lists)
step = 2
group = count / step
while group > 0:
for i in range(0, group):
j = i + group
while j < count:
k = j - group
key = lists[j]
while k >= 0:
if lists[k] > key:
lists[k + group] = lists[k]
lists[k] = key
k -= group
j += group
group /= step
return lists
'''
冒泡排序重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
'''
def bubble_sort(lists):
# 冒泡排序
count = len(lists)
for i in range(0, count):
for j in range(i + 1, count):
if lists[i] > lists[j]:
temp = lists[j]
lists[j] = lists[i]
lists[i] = temp
return lists
'''
快速排序
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
'''
def quick_sort(lists, left, right):
# 快速排序
if left >= right:
return lists
key = lists[left]
low = left
high = right
while left < right:
while left < right and lists[right] >= key:
right -= 1
lists[left] = lists[right]
while left < right and lists[left] <= key:
left += 1
lists[right] = lists[left]
lists[right] = key
quick_sort(lists, low, left - 1)
quick_sort(lists, left + 1, high)
return lists
'''
直接选择排序
第 1 趟，在待排序记录 r[1] ~ r[n] 中选出最小的记录，将它与 r[1] 交换；
第 2 趟，在待排序记录 r[2] ~ r[n] 中选出最小的记录，将它与 r[2] 交换；
以此类推，第 i 趟在待排序记录 r[i] ~ r[n] 中选出最小的记录，将它与 r[i] 交换，使有序序列不断增长直到全部排序完毕。
'''
def select_sort(lists):
# 选择排序
count = len(lists)
for i in range(0, count):
min = i
for j in range(i + 1, count):
if lists[min] > lists[j]:
min = j
temp = lists[min]
lists[min] = lists[i]
lists[i] = temp
return lists
'''
堆排序 (Heapsort) 是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。
可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即 A[PARENT[i]] >= A[i]。
在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
'''
# 调整堆
def adjust_heap(lists, i, size):
lchild = 2 * i + 1
rchild = 2 * i + 2
max = i
if i < size / 2:
if lchild < size and lists[lchild] > lists[max]:
max = lchild
if rchild < size and lists[rchild] > lists[max]:
max = rchild
if max != i:
lists[max], lists[i] = lists[i], lists[max]
adjust_heap(lists, max, size)
# 创建堆
def build_heap(lists, size):
for i in range(0, (size/2))[::-1]:
adjust_heap(lists, i, size)
# 堆排序
def heap_sort(lists):
size = len(lists)
build_heap(lists, size)
for i in range(0, size)[::-1]:
lists[0], lists[i] = lists[i], lists[0]
adjust_heap(lists, 0, i)
'''
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法 （Divide and Conquer） 的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并过程为：
比较 a[i] 和 a[j] 的大小，若 a[i]≤a[j]，则将第一个有序表中的元素 a[i] 复制到 r[k] 中，并令 i 和 k 分别加上 1；
否则将第二个有序表中的元素 a[j] 复制到 r[k] 中，并令 j 和 k 分别加上 1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到 r 中从下标 k 到下标 t 的单元。归并排序的算法我们通常用递归实现，先把待排序区间 [s,t] 以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间 [s,t]。
'''
def merge(left, right):
i, j = 0, 0
result = []
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result
def merge_sort(lists):
# 归并排序
if len(lists) <= 1:
return lists
num = len(lists) / 2
left = merge_sort(lists[:num])
right = merge_sort(lists[num:])
return merge(left, right)
'''
基数排序 （radix sort） 属于“分配式排序” （distribution sort），又称“桶子法” （bucket sort） 或 bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，借以达到排序的作用，基数排序法是属于稳定性的排序。
其时间复杂度为 O (nlog(r)m)，其中 r 为所采取的基数，而 m 为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
'''
import math
def radix_sort(lists, radix=10):
k = int(math.ceil(math.log(max(lists), radix)))
bucket = [[] for i in range(radix)]
for i in range(1, k+1):
for j in lists:
bucket[j/(radix**(i-1)) % (radix**i)].append(j)
del lists[:]
for z in bucket:
lists += z
del z[:]
return lists
---------------------
作者：CRazyDOgen
来源：CSDN
原文：https://blog.csdn.net/jipang6225/article/details/79975312
版权声明：本文为博主原创文章，转载请附上博文链接！
7. 基于C语言的几种排序算法的分析
相关知识介绍（所有定义只为帮助读者理解相关概念，并非严格定义）：
1、稳定排序和非稳定排序
简单地说就是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就
说这种排序方法是稳定的。反之，就是非稳定的。
比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为a1,a2,a4,a3,a5，
则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4,
a2,a3,a5就不是稳定的了。
2、内排序和外排序
在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序；
在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。
3、算法的时间复杂度和空间复杂度
所谓算法的时间复杂度，是指执行算法所需要的计算工作量。
一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。
================================================================================
*/
/*
================================================
功能：选择排序
输入：数组名称（也就是数组首地址）、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述：
在要排序的一组数中，选出最小的一个数与第一个位置的数交换；
然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环
到倒数第二个数和最后一个数比较为止。
选择排序是不稳定的。算法复杂度O(n2)--[n的平方]
=====================================================
*/
void select_sort(int *x, int n)
{
int i, j, min, t;
for (i=0; i<n-1; i++) /*要选择的次数：0~n-2共n-1次*/
{
min = i; /*假设当前下标为i的数最小，比较后再调整*/
for (j=i+1; j<n; j++)/*循环找出最小的数的下标是哪个*/
{
if (*(x+j) < *(x+min))
{
min = j; /*如果后面的数比前面的小，则记下它的下标*/
}
}
if (min != i) /*如果min在循环中改变了，就需要交换数据*/
{
t = *(x+i);
*(x+i) = *(x+min);
*(x+min) = t;
}
}
}
/*
================================================
功能：直接插入排序
输入：数组名称（也就是数组首地址）、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述：
在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排
好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数
也是排好顺序的。如此反复循环，直到全部排好顺序。
直接插入排序是稳定的。算法时间复杂度O(n2)--[n的平方]
=====================================================
*/
void insert_sort(int *x, int n)
{
int i, j, t;
for (i=1; i<n; i++) /*要选择的次数：1~n-1共n-1次*/
{
/*
暂存下标为i的数。注意：下标从1开始，原因就是开始时
第一个数即下标为0的数，前面没有任何数，单单一个，认为
它是排好顺序的。
*/
t=*(x+i);
for (j=i-1; j>=0 && t<*(x+j); j--) /*注意：j=i-1，j--，这里就是下标为i的数，在它前面有序列中找插入位置。*/
{
*(x+j+1) = *(x+j); /*如果满足条件就往后挪。最坏的情况就是t比下标为0的数都小，它要放在最前面，j==-1，退出循环*/
}
*(x+j+1) = t; /*找到下标为i的数的放置位置*/
}
}
/*
================================================
功能：冒泡排序
输入：数组名称（也就是数组首地址）、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述：
在要排序的一组数中，对当前还未排好序的范围内的全部数，自上
而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较
小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要
求相反时，就将它们互换。
下面是一种改进的冒泡算法，它记录了每一遍扫描后最后下沉数的
位置k，这样可以减少外层循环扫描的次数。
冒泡排序是稳定的。算法时间复杂度O(n2)--[n的平方]
=====================================================
*/
void bubble_sort(int *x, int n)
{
int j, k, h, t;
for (h=n-1; h>0; h=k) /*循环到没有比较范围*/
{
for (j=0, k=0; j<h; j++) /*每次预置k=0，循环扫描后更新k*/
{
if (*(x+j) > *(x+j+1)) /*大的放在后面，小的放到前面*/
{
t = *(x+j);
*(x+j) = *(x+j+1);
*(x+j+1) = t; /*完成交换*/
k = j; /*保存最后下沉的位置。这样k后面的都是排序排好了的。*/
}
}
}
}
/*
================================================
功能：希尔排序
输入：数组名称（也就是数组首地址）、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述：
在直接插入排序算法中，每次插入一个数，使有序序列只增加1个节点，
并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离（称为
增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除
多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现
了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中
记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量
对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成
一组，排序完成。
下面的函数是一个希尔排序算法的一个实现，初次取序列的一半为增量，
以后每次减半，直到增量为1。
希尔排序是不稳定的。
=====================================================
*/
void shell_sort(int *x, int n)
{
int h, j, k, t;
for (h=n/2; h>0; h=h/2) /*控制增量*/
{
for (j=h; j<n; j++) /*这个实际上就是上面的直接插入排序*/
{
t = *(x+j);
for (k=j-h; (k>=0 && t<*(x+k)); k-=h)
{
*(x+k+h) = *(x+k);
}
*(x+k+h) = t;
}
}
}
/*
================================================
功能：快速排序
输入：数组名称（也就是数组首地址）、数组中起止元素的下标
================================================
*/
/*
====================================================
算法思想简单描述：
快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟
扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次
扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只
减少1。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）
的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理
它左右两边的数，直到基准点的左右只有一个元素为止。它是由
C.A.R.Hoare于1962年提出的。
显然快速排序可以用递归实现，当然也可以用栈化解递归实现。下面的
函数是用递归实现的，有兴趣的朋友可以改成非递归的。
快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n)，最坏O(n2)
=====================================================
*/
void quick_sort(int *x, int low, int high)
{
int i, j, t;
if (low < high) /*要排序的元素起止下标，保证小的放在左边，大的放在右边。这里以下标为low的元素为基准点*/
{
i = low;
j = high;
t = *(x+low); /*暂存基准点的数*/
while (i<j) /*循环扫描*/
{
while (i<j && *(x+j)>t) /*在右边的只要比基准点大仍放在右边*/
{
j--; /*前移一个位置*/
}
if (i<j)
{
*(x+i) = *(x+j); /*上面的循环退出：即出现比基准点小的数，替换基准点的数*/
i++; /*后移一个位置，并以此为基准点*/
}
while (i<j && *(x+i)<=t) /*在左边的只要小于等于基准点仍放在左边*/
{
i++; /*后移一个位置*/
}
if (i<j)
{
*(x+j) = *(x+i); /*上面的循环退出：即出现比基准点大的数，放到右边*/
j--; /*前移一个位置*/
}
}
*(x+i) = t; /*一遍扫描完后，放到适当位置*/
quick_sort(x,low,i-1); /*对基准点左边的数再执行快速排序*/
quick_sort(x,i+1,high); /*对基准点右边的数再执行快速排序*/
}
}
/*
================================================
功能：堆排序
输入：数组名称（也就是数组首地址）、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述：
堆排序是一种树形选择排序，是对直接选择排序的有效改进。
堆的定义如下：具有n个元素的序列（h1,h2,...,hn),当且仅当
满足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)
时称之为堆。在这里只讨论满足前者条件的堆。
由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项。完全二叉树可以
很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。
初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储顺序，
使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点
交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点
的堆，并对它们作交换，最后得到有n个节点的有序序列。
从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素
交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数
实现排序的函数。
堆排序是不稳定的。算法时间复杂度O(nlog2n)。
*/
/*
功能：渗透建堆
输入：数组名称（也就是数组首地址）、参与建堆元素的个数、从第几个元素开始
*/
void sift(int *x, int n, int s)
{
int t, k, j;
t = *(x+s); /*暂存开始元素*/
k = s; /*开始元素下标*/
j = 2*k + 1; /*右子树元素下标*/
while (j<n)
{
if (j<n-1 && *(x+j) < *(x+j+1))/*判断是否满足堆的条件：满足就继续下一轮比较，否则调整。*/
{
j++;
}
if (t<*(x+j)) /*调整*/
{
*(x+k) = *(x+j);
k = j; /*调整后，开始元素也随之调整*/
j = 2*k + 1;
}
else /*没有需要调整了，已经是个堆了，退出循环。*/
{
break;
}
}
*(x+k) = t; /*开始元素放到它正确位置*/
}
/*
功能：堆排序
输入：数组名称（也就是数组首地址）、数组中元素个数
*/
void heap_sort(int *x, int n)
{
int i, k, t;
int *p;
for (i=n/2-1; i>=0; i--)
{
sift(x,n,i); /*初始建堆*/
}
for (k=n-1; k>=1; k--)
{
t = *(x+0); /*堆顶放到最后*/
*(x+0) = *(x+k);
*(x+k) = t;
sift(x,k,0); /*剩下的数再建堆*/
}
}
void main()
{
#define MAX 4
int *p, i, a[MAX];
/*录入测试数据*/
p = a;
printf("Input %d number for sorting :\n",MAX);
for (i=0; i<MAX; i++)
{
scanf("%d",p++);
}
printf("\n");
/*测试选择排序*/
p = a;
select_sort(p,MAX);
/**/
/*测试直接插入排序*/
/*
p = a;
insert_sort(p,MAX);
*/
/*测试冒泡排序*/
/*
p = a;
insert_sort(p,MAX);
*/
/*测试快速排序*/
/*
p = a;
quick_sort(p,0,MAX-1);
*/
/*测试堆排序*/
/*
p = a;
heap_sort(p,MAX);
*/
for (p=a, i=0; i<MAX; i++)
{
printf("%d ",*p++);
}
printf("\n");
system("pause");
}
8. 设有长度为n的数组a，请设计直接插入排序算法
void lnsertSort(SeqList R)
{ //对顺序表R中的记录R[1..n]按递增序进行插入排序
int i，j；
for(i=2;i<=n；i++) //依次插入R[2]，…，R[n]
if(R[i].key<R[i-1].key){//若R[i].key大于等于有序区中所有的keys，则R[i]
//应在原有位置上
R[0]=R[i];j=i-1; //R[0]是哨兵，且是R[i]的副本
do{ //从右向左在有序区R[1．．i-1]中查找R[i]的插入位置
R[j+1]=R[j]； //将关键字大于R[i].key的记录后移
j-- ；
}while(R[0].key<R[j].key)； //当R[i].key≥R[j].key时终止
R[j+1]=R[0]； //R[i]插入到正确的位置上
}//endif
}//InsertSort
9. 排序算法如何实现 C++
一、简单排序算法
由于程序比较简单，所以没有加什么注释。所有的程序都给出了完整的运行代码，并在我的VC环境
下运行通过。因为没有涉及MFC和WINDOWS的内容，所以在BORLAND C++的平台上应该也不会有什么
问题的。在代码的后面给出了运行过程示意，希望对理解有帮助。
1.冒泡法：
这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡：
#include <iostream.h>
void BubbleSort(int* pData,int Count)
{
int iTemp;
for(int i=1;i<Count;i++)
{
for(int j=Count-1;j>=i;j--)
{
if(pData[j]<pData[j-1])
{
iTemp = pData[j-1];
pData[j-1] = pData[j];
pData[j] = iTemp;
}
}
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
BubbleSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情况)
第一轮：10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交换3次)
第二轮：7,10,9,8->7,10,8,9->7,8,10,9(交换2次)
第一轮：7,8,10,9->7,8,9,10(交换1次)
循环次数：6次
交换次数：6次
其他：
第一轮：8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交换2次)
第二轮：7,8,10,9->7,8,10,9->7,8,10,9(交换0次)
第一轮：7,8,10,9->7,8,9,10(交换1次)
循环次数：6次
交换次数：3次
上面我们给出了程序段，现在我们分析它：这里，影响我们算法性能的主要部分是循环和交换， 显然，次数越多，性能就越差。从上面的程序我们可以看出循环的次数是固定的，为1+2+...+n-1。 写成公式就是1/2*(n-1)*n。 现在注意，我们给出O方法的定义：
若存在一常量K和起点n0，使当n>=n0时，有f(n)<=K*g(n),则f(n) = O(g(n))。（呵呵，不要说没 学好数学呀，对于编程数学是非常重要的！！！）
现在我们来看1/2*(n-1)*n，当K=1/2，n0=1，g(n)=n*n时，1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n) =O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。 再看交换。从程序后面所跟的表可以看到，两种情况的循环相同，交换不同。其实交换本身同数据源的 有序程度有极大的关系，当数据处于倒序的情况时，交换次数同循环一样（每次循环判断都会交换）， 复杂度为O(n*n)。当数据为正序，将不会有交换。复杂度为O(0)。乱序时处于中间状态。正是由于这样的 原因，我们通常都是通过循环次数来对比算法。
2.交换法：
交换法的程序最清晰简单，每次用当前的元素一一的同其后的元素比较并交换。
#include <iostream.h>
void ExchangeSort(int* pData,int Count)
{
int iTemp;
for(int i=0;i<Count-1;i++)
{
for(int j=i+1;j<Count;j++)
{
if(pData[j]<pData[i])
{
iTemp = pData[i];
pData[i] = pData[j];
pData[j] = iTemp;
}
}
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
ExchangeSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情况)
第一轮：10,9,8,7->9,10,8,7->8,10,9,7->7,10,9,8(交换3次)
第二轮：7,10,9,8->7,9,10,8->7,8,10,9(交换2次)
第一轮：7,8,10,9->7,8,9,10(交换1次)
循环次数：6次
交换次数：6次
其他：
第一轮：8,10,7,9->8,10,7,9->7,10,8,9->7,10,8,9(交换1次)
第二轮：7,10,8,9->7,8,10,9->7,8,10,9(交换1次)
第一轮：7,8,10,9->7,8,9,10(交换1次)
循环次数：6次
交换次数：3次
从运行的表格来看，交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样 也是1/2*(n-1)*n，所以算法的复杂度仍然是O(n*n)。由于我们无法给出所有的情况，所以 只能直接告诉大家他们在交换上面也是一样的糟糕（在某些情况下稍好，在某些情况下稍差）。
3.选择法：
现在我们终于可以看到一点希望：选择法，这种方法提高了一点性能（某些情况下） 这种方法类似我们人为的排序习惯：从数据中选择最小的同第一个值交换，在从省下的部分中 选择最小的与第二个交换，这样往复下去。
#include <iostream.h>
void SelectSort(int* pData,int Count)
{
int iTemp;
int iPos;
for(int i=0;i<Count-1;i++)
{
iTemp = pData[i];
iPos = i;
for(int j=i+1;j<Count;j++)
{
if(pData[j]<iTemp)
{
iTemp = pData[j];
iPos = j;
}
}
pData[iPos] = pData[i];
pData[i] = iTemp;
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
SelectSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情况)
第一轮：10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(交换1次)
第二轮：7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(交换1次)
第一轮：7,8,9,10->(iTemp=9)7,8,9,10(交换0次)
循环次数：6次
交换次数：2次
其他：
第一轮：8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交换1次)
第二轮：7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,9(交换1次)
第一轮：7,8,10,9->(iTemp=9)7,8,9,10(交换1次)
循环次数：6次
交换次数：3次
遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。所以算法复杂度为O(n*n)。 我们来看他的交换。由于每次外层循环只产生一次交换（只有一个最小值）。所以f(n)<=n 所以我们有f(n)=O(n)。所以，在数据较乱的时候，可以减少一定的交换次数。
4.插入法：
插入法较为复杂，它的基本工作原理是抽出牌，在前面的牌中寻找相应的位置插入，然后继续下一张
#include <iostream.h>
void InsertSort(int* pData,int Count)
{
int iTemp;
int iPos;
for(int i=1;i<Count;i++)
{
iTemp = pData[i];
iPos = i-1;
while((iPos>=0) && (iTemp<pData[iPos]))
{
pData[iPos+1] = pData[iPos];
iPos--;
}
pData[iPos+1] = iTemp;
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
InsertSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情况)
第一轮：10,9,8,7->9,10,8,7(交换1次)(循环1次)
第二轮：9,10,8,7->8,9,10,7(交换1次)(循环2次)
第一轮：8,9,10,7->7,8,9,10(交换1次)(循环3次)
循环次数：6次
交换次数：3次
其他：
第一轮：8,10,7,9->8,10,7,9(交换0次)(循环1次)
第二轮：8,10,7,9->7,8,10,9(交换1次)(循环2次)
第一轮：7,8,10,9->7,8,9,10(交换1次)(循环1次)
循环次数：4次
交换次数：2次
上面结尾的行为分析事实上造成了一种假象，让我们认为这种算法是简单算法中最好的，其实不是， 因为其循环次数虽然并不固定，我们仍可以使用O方法。从上面的结果可以看出，循环的次数f(n)<= 1/2*n*(n-1)<=1/2*n*n。所以其复杂度仍为O(n*n)（这里说明一下，其实如果不是为了展示这些简单 排序的不同，交换次数仍然可以这样推导）。现在看交换，从外观上看，交换次数是O(n)（推导类似 选择法），但我们每次要进行与内层循环相同次数的‘=’操作。正常的一次交换我们需要三次‘=’ 而这里显然多了一些，所以我们浪费了时间。
最终，我个人认为，在简单排序算法中，选择法是最好的。
二、高级排序算法：
高级排序算法中我们将只介绍这一种，同时也是目前我所知道（我看过的资料中）的最快的。 它的工作看起来仍然象一个二叉树。首先我们选择一个中间值middle程序中我们使用数组中间值，然后 把比它小的放在左边，大的放在右边（具体的实现是从两边找，找到一对后交换）。然后对两边分别使 用这个过程（最容易的方法——递归）。
1.快速排序：
#include <iostream.h>
void run(int* pData,int left,int right)
{
int i,j;
int middle,iTemp;
i = left;
j = right;
middle = pData[(left+right)/2]; //求中间值
do{
while((pData[i]<middle) && (i<right))//从左扫描大于中值的数
i++;
while((pData[j]>middle) && (j>left))//从右扫描大于中值的数
j--;
if(i<=j)//找到了一对值
{
//交换
iTemp = pData[i];
pData[i] = pData[j];
pData[j] = iTemp;
i++;
j--;
}
}while(i<=j);//如果两边扫描的下标交错，就停止（完成一次）
//当左边部分有值(left<j)，递归左半边
if(left<j)
run(pData,left,j);
//当右边部分有值(right>i)，递归右半边
if(right>i)
run(pData,i,right);
}
void QuickSort(int* pData,int Count)
{
run(pData,0,Count-1);
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
QuickSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
这里我没有给出行为的分析，因为这个很简单，我们直接来分析算法：首先我们考虑最理想的情况
1.数组的大小是2的幂，这样分下去始终可以被2整除。假设为2的k次方，即k=log2(n)。
2.每次我们选择的值刚好是中间值，这样，数组才可以被等分。
第一层递归，循环n次，第二层循环2*(n/2)......
所以共有n+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n
所以算法复杂度为O(log2(n)*n)
其他的情况只会比这种情况差，最差的情况是每次选择到的middle都是最小值或最大值，那么他将变 成交换法（由于使用了递归，情况更糟）。但是你认为这种情况发生的几率有多大？？呵呵，你完全 不必担心这个问题。实践证明，大多数的情况，快速排序总是最好的。 如果你担心这个问题，你可以使用堆排序，这是一种稳定的O(log2(n)*n)算法，但是通常情况下速度要慢 于快速排序（因为要重组堆）。
三、其他排序
1.双向冒泡：
通常的冒泡是单向的，而这里是双向的，也就是说还要进行反向的工作。 代码看起来复杂，仔细理一下就明白了，是一个来回震荡的方式。 写这段代码的作者认为这样可以在冒泡的基础上减少一些交换（我不这么认为，也许我错了）。 反正我认为这是一段有趣的代码，值得一看。
#include <iostream.h>
void Bubble2Sort(int* pData,int Count)
{
int iTemp;
int left = 1;
int right =Count -1;
int t;
do {
//正向的部分
for(int i=right;i>=left;i--)
{
if(pData[i]<pData[i-1])
{
iTemp = pData[i];
pData[i] = pData[i-1];
pData[i-1] = iTemp;
t = i;
}
}
left = t+1;
//反向的部分
for(i=left;i<right+1;i++)
{
if(pData[i]<pData[i-1])
{
iTemp = pData[i];
pData[i] = pData[i-1];
pData[i-1] = iTemp;
t = i;
}
}
right = t-1;
}while(left<=right);
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
Bubble2Sort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
2.SHELL排序
这个排序非常复杂，看了程序就知道了。 首先需要一个递减的步长，这里我们使用的是9、5、3、1（最后的步长必须是1）。 工作原理是首先对相隔9-1个元素的所有内容排序，然后再使用同样的方法对相隔5-1个元素的排序，以次类推。
#include <iostream.h>
void ShellSort(int* pData,int Count)
{
int step[4];
step[0] = 9;
step[1] = 5;
step[2] = 3;
step[3] = 1;
int i,Temp;
int k,s,w;
for(int i=0;i<4;i++)
{
k = step[i];
s = -k;
for(int j=k;j<Count;j++)
{
iTemp = pData[j];
w = j-k;//求上step个元素的下标
if(s ==0)
{
s = -k;
s++;
pData[s] = iTemp;
}
while((iTemp<pData[w]) && (w>=0) && (w<=Count))
{
pData[w+k] = pData[w];
w = w-k;
}
pData[w+k] = iTemp;
}
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4,3,2,1,-10,-1};
ShellSort(data,12);
for (int i=0;i<12;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
呵呵，程序看起来有些头疼。不过也不是很难，把s==0的块去掉就轻松多了，这里是避免使用0 步长造成程序异常而写的代码。这个代码我认为很值得一看。 这个算法的得名是因为其发明者的名字D.L.SHELL。依照参考资料上的说法：“由于复杂的数学原因 避免使用2的幂次步长，它能降低算法效率。”另外算法的复杂度为n的1.2次幂。同样因为非常复杂并 “超出本书讨论范围”的原因（我也不知道过程），我们只有结果了
10. 使用C语言或C++设计实现一个算法，用以对两个非递减有序表A、B进行合并
直接插入排序就能完成，将其中一个顺序表中的每个元素按直接插入排序的算法依次插入另一个顺序表中