成都创新互联是一家专业提供
白城企业网站建设,专注与成都做网站、成都网站建设、
html5、小程序制作等业务。10年已为白城众多企业、政府机构等服务。创新互联专业的建站公司优惠进行中。
选择排序
图像化显示： 
选择排序的基本思想：从待排序序列中找到最小（大）的元素，存放到序列起始位置，缩小排序范围，再找当前序列最小（大）的元素，放在起始位置之后，直到所有数据都被排完。
时间复杂度=O(n^2)
空间复杂度=O(1)
最好情况：已经有序 交换次数O(1)
最坏情况：逆序 交换次数O(n-1)
下面是c++版本的代码实现
#include
using namespace std;
//初始版本，每次找到最小的
void SelectSort(int *a,size_t size)
{
//比较次数：n*(n-1)/2
for(size_t i=0;ia[j])
{
min=j;
}
}
//赋值次数：0~3(n-1)之间
if(min!=i)
{
swap(a[min],a[i]);
}
}
}
//改进版本，每次确定大的和最小的
void SelectSort(int *a,size_t size)
{
//1/2数列的长度
for(size_t left=0,right=size-1;lefta[j])
{
min=j;
}
if(a[max]堆排序
堆排序的基本思想：利用堆这种数据结构进行选择排序。
堆：堆是一个完全二叉树，其任意一个非叶子结点满足：
（大堆）a[key]>a[key*2+1]&&a[key]>a[key*2+2];(非叶子结点大于任意一个孩子结点)
（最小堆）a[key]升序：由大堆（根结点是所有结点中的大值，任意一个结点都比它的孩子结点的值要大）将顶部元素与末尾元素交换，减小堆中元素个数，每次都将当前堆中大的数排到正确的位置，直到只有一个根结点，这种通过二叉树的结构的排序，其n个数每次的找大的数的执行次数是O(logn)即一个n个数的二叉树深度，共有n个数所以最终的时间复杂度是O(nlogn)
时间复杂度：O(nlogn)
空间复杂度：O(1)
降序：与之相反
图形化表示：
下面是c++版本的代码实现
#include
using namespace std;
//建局部堆----向下调整
void AdjustDown(int *a,int size,int index)
{
parent=index;
int child=parent*2+1;
while(childa[child])
{
child++;
}
//如果孩子结点大于父结点，交换，并且看交换完之后，这个局部是否还满足条件
if(a[child]>a[parent])
{
swap(a[child],a[parent]);
parent=child;
child=parent*2=1；
}
//如果孩子结点不大于父节点，可以直接跳出
else
{
break;
}
}
}
//堆排序
void HeapSort(int *a,int size)
{
//将数组转化成堆----O(logn)
for(int i=(size-2)/2;i>=0;i--)
{
AdjustDown(a,size,i);
}
//O(nlogn)
for(int i=0;i#include
using namespace std;
//直接插入排序
void InsertSort(int *a,size_t size)
{
for(size_t i=1;i=0&&a[end]>temp)
{
a[end+1]=a[end];
end--;
}
//当end所在位置的数比temp小时，while跳出循环，end指向带插入位置的前一个位置
//所以end+1，才是temp该放的位置
a[end+1]=temp;
}
}
希尔排序
希尔排序是插入排序的优化版本，可以尽快的让小数往前走，大数往后走。
方法：把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
优点：对已经有序的序列，效率高，可以达到线性效率即O(n)
缺点：每次只能移动一位（一般情况下的低效）
时间复杂度：O(n^2)
空间复杂度：O(1)
图形化显示：
以下是c++代码实现
#include
using namespace std;
void ShellSort(int *a,int size)
{
//增量值得设定
int gap=size;
while (gap>1)
{
gap=gap/3+1;
for (size_t i=gap;i=0&&temp归并排序
归并排序应用的是分治法的思想，将一个无序序列，分成两部分，再将这两部分，看成子问题，在进行划分，一直到序列中只有一个数字的时候，当前子序列就有序了，然后将这些个子序列进行有序合并，知道合并成整个序列。速度仅次于快速排序，为稳定排序算法。
简洁的说就是：无序序列-----划分成不可再分子序列----子序列有序合并----有序序列
时间复杂度为O(nlogn) 这是该算法中最好、最坏和平均的时间性能。
空间复杂度为 O(n)
图形化显示：
以下是c++实现(递归和非递归版本)
//合并
void GetMerge(int *a,int begin1,int end1,int begin2,int end2,int *temp)
{
int i=0;
while(begin1<=end1&&begin2<=end2)
{
if (a[begin1]算法思想：
冒泡排序算法的运作如下：（从后往前）
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
优点：稳定性算法
缺点：时间复杂度高
时间复杂度：O(N^2)（平均时间复杂度）
空间复杂度：O(1)
以下是c++代码
void BubbleSort(int *a1,size_t size)
{
for (size_t i=0;ia[j+1])
{
swap(a[j],a[j+1]);
}
}
}
}快速排序是对冒泡排序的一种改进。
它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。其中作为分隔数据的关键数据我们成为Key,当key为当前数列中的大值时，快速排序就是冒泡排序.
最好情况：O(nlogn)
最坏情况：O(n^2)
时间复杂度:O(nlogn)
空间复杂度：O(1)
C++代码实现
（1）基础版---选择数列的最后一个数作为key，递归快排
//单趟排序
int PartionSort(int *a1,int left,int right)
{
int begin=left;
int end=right-1;
int key=a[right];
while(beginbegin&&a[end]>key)
{
end--;
}
if (end!=begin)
{
swap(a[end],a[begin]);
end--;
begin++;
}
}
if (a[begin]>key)
{
swap(a[begin],a[right]);
return begin;
}
else
{
return begin;
}
}
//快速排序--递归思想
void QuickSort(int *a1,int left,int right)
{
assert(a);
if (left（2）改进版：选择key值时，用三数取中，避免最坏情况的发生。
//单趟排序
int PartionSort(int *a1,int left,int right)
{
int begin=left;
int end=right-1;
int key=a[right];
while(beginbegin&&a[end]>key)
{
end--;
}
if (end!=begin)
{
swap(a[end],a[begin]);
}
}
if (a[begin]>key)
{
swap(a[begin],a[right]);
return begin;
}
else
{
return right;
}
}
//快速排序---三数取中
void QuickSort(int *a1,int left,int right)
{
assert(a);
int mid=left+(right-left)/2;
if (lefta[mid])
{
swap(a[mid],a[left]);
}
}
else
{
if (a[left]a[mid])
{
swap(a[mid],a[right]);
}
}
swap(a[mid],a[right]);
int boundary=PartionSort(a,left,right);
QuickSort(a,left,boundary-1);
QuickSort(a,boundary+1,right);
}
}（3）对每次排序进行优化，当数列中个数小于13（STL中这样实现的），应用插入排序。
//单趟排序
int PartionSort(int *a1,int left,int right)
{
int begin=left;
int end=right-1;
int key=a[right];
while(beginbegin&&a[end]>key)
{
end--;
}
if (end!=begin)
{
swap(a[end],a[begin]);
}
}
if (a[begin]>key)
{
swap(a[begin],a[right]);
return begin;
}
else
{
return right;
}
}
//快速排序中个数少时用插入排序
void QuickSort(int *a1,int left,int right)
{
assert(a);
if(right-left<13)
{
InsertSort(a,right-left+1);
}
if (left(4)快排的非递归版本（栈实现）
//快速排序非递归实现
//手动利用栈来存储每次分块快排的起始点，栈非空时循环获取中轴入栈。
void QuickSort(int *a1,int left,int right)
{
stack s1;
if(left1)
{
s1.push(left);
s1.push(boundary-1);
}
if (right-(boundary+1)>1)
{
s1.push(boundary+1);
s1.push(right);
}
while (!s1.empty())
{
int r=s1.top();
s1.pop();
int l=s1.top();
s1.pop();
boundary=PartionSort(a,l,r);
if (boundary-1-l>1)
{
s1.push(l);
s1.push(boundary-1);
}
if (r-(boundary+1)>1)
{
s1.push(boundary+1);
s1.push(r);
}
}
}
}(5)模拟单链表中的快排
int PartionSortLink(int *a1,int left,int right)
{
int prev=left-1;
int cur=left;
int key=a[right];
while(cur创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
本文题目：排序大荟萃-创新互联
转载来于：http://cdxtjz.cn/article/ccjcei.html
