无用排序算法

㈠ 排序算法课程设计

// 各种排序算法汇总.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;

#include <stack>
#include <time.h>
#include <stdlib.h>

template < typename T >
class SqList
{
private:
int length;
T * r;
public://接口
SqList(int n = 0);//构造长度为n的数组
~SqList()
{
length = 0;
delete r;
r = NULL;
}
void InsertSort();//顺序插入排序
void DisPlay();//输出元素
void BInsertSort();//折半插入排序
void ShellSort(int dlta[],int t);//希尔排序
void QuickSort();//快速排序
void SelectSort();//简单选择排序
void BubbleSort();//改进冒泡排序
void Bubble_Sort2();//相邻两趟是反方向起泡的冒泡排序算法
void Bubble_Sort3();//对相邻两趟反方向算法进行化简,循环体中只包含一次冒泡
void HeapSort();//堆排序
void Build_Heap_Sort();//堆排序由小到大序号建立大根堆
void MergeSort();//归并排序
void OE_Sort();//奇偶交换排序的算法

void Q_Sort_NotRecurre();//非递归快速排序
void HeapSort_3();//三叉堆排序

public://调用
void ShellInsert(int dk);//一趟希尔排序
void QSort(int low,int high);//快速排序
int Partition(int low,int high);//一趟快速排序
int SelectMinKey(int i);//从i到length中选择最小值下标
void HeapAdjust(int s,int m);//调整s的位置,其中s+1~m有序
void HeapAdjust_3(int s,int m);//三叉堆****调整s的位置,其中s+1~m有序
void Merge(T SR[],T TR[],int i,int m,int n);//归并
void MSort(T SR[],T TR1[],int s,int t);//归并
void Easy_Sort(int low,int high);//3个数直接排序
void Build_Heap(int len);//从低下标到高下标逐个插入建堆的算法***建立大根堆**但为排序

};
template < typename T >
SqList<T>::SqList(int n = 0)
{
//srand( time(0) );
length = n;
r=new T[length+1];
T t;
cout<<"随机生成"<<n<<"个值:"<<endl;
for (int i=1;i<=length;i++)
{
//cin>>t;
r[i] = rand()%1000;
//r[i] = t;
}
for (int i=1; i<=length;i++)
cout<<r[i]<<",";
cout<<endl;
}
template < typename T >
void SqList<T>::InsertSort()
{
int i,j;
for (i=2;i<=length;i++)
{
if (r[i]<r[i-1])
{
r[0]=r[i];
r[i]=r[i-1];
for (j=i-2;r[0]<r[i-2];j--)
r[j+1]=r[j];
r[j+1]=r[0];
}
}
}
template < typename T >
void SqList<T>::DisPlay()
{
int i;
cout<<length<<" 元素为："<<endl;
for (i = 1;i < length+1;i++ )
{
cout<<r[i]<<" ,";
}
cout<<endl;
}
template < typename T >
void SqList<T>::BInsertSort()
{
int i, j, m;
int low,high;
for (i = 2;i<= length;i++)
{
r[0]=r[i];
low=1;
high=i-1;
while (low<=high)
{
m = (low+high)/2;
if ( r[0] < r[m] )
high=m-1;
else
low=m+1;
}
for ( j=i-1;j >=high+1; j--)
{
r[j+1] = r[j];
}
r[high+1] = r[0];
}
}

template < typename T >
void SqList<T>::ShellInsert(int dk)
{
int i,j;
for (i=dk+1;i<=length;i++)
if (r[i] < r[i-dk])
{
r[0] = r[i];
for ( j=i-dk; j>0 && r[0] < r[j]; j-=dk)
{
r[j+dk]=r[j];
}
r[j+dk] = r[0];
}
}
template < typename T >
void SqList<T>::ShellSort(int dlta[],int t)
{
int k=0;
for (;k<t;k++)
{
ShellInsert(dlta[k]);
}
}
template < typename T >
int SqList<T>::Partition(int low,int high)
{
int pivotkey;
r[0] = r[low];//记录枢轴值
pivotkey = r[low];
while (low < high)
{
while (low < high&& r[high] >= pivotkey)
high--;
r[low] = r[high];
while (low < high&& r[low] <= pivotkey)
low++;
r[high] = r[low];
}
r[low] = r[0];//枢轴记录到位
return low;//返回枢轴位置
}
template < typename T >
void SqList<T>::QSort(int low,int high)
{
int pivotloc;
if (low < high)
{
pivotloc = Partition(low,high);
QSort(low,pivotloc-1);
QSort(pivotloc+1,high);
}
}
template < typename T >
void SqList<T>::QuickSort()
{
QSort(1,length);
}
template < typename T >
int SqList<T>::SelectMinKey(int i)
{
int j,min=i;
for (j=i;j <= length;j++)
{
if (r[min] > r[j])
{
min = j;
}
}
return min;
}
template < typename T >
void SqList<T>::SelectSort()
{
int i,j;
T t;
for (i=1;i < length;i++)//循环length-1次不是length次
{
j=SelectMinKey(i);
if (i != j)
{
t= r[j];
r[j]=r[i];
r[i]=t;
}
}
}
template < typename T >
void SqList<T>::BubbleSort()
{
int i,j;
int flag=1;//标识位，如果出现0，则没有交换，立即停止
T t;
for (i=1;i < length && flag;i++)
{
flag = 0;
for (j=length-1;j>=i;j--)
if (r[j]>r[j+1])
{
t=r[j];
r[j]=r[j+1];
r[j+1]=t;
flag=1;
}
}
}
template < typename T >
void SqList<T>::Bubble_Sort2()
{
bool change = true;
int low = 1, high = length;
int i;
T t;
while ( (low < high) && change )
{
change = false;
for ( i = low; i < high; i++ )
{
if ( r[i] > r[i+1] )
{
t = r[i];
r[i] = r[i+1];
r[i+1] = t;
change = true;
}
}
high-=1;
for ( i = high; i > low; i-- )
{
if ( r[i] < r[i-1] )
{
t = r[i];
r[i] = r[i-1];
r[i-1] = t;
change = true;
}
}
low+=1;
}
}

template < typename T >
void SqList<T>::Bubble_Sort3()
{
int i,d=1;
bool change = true;
int b[3] = {1,0,length};//b[0]为冒泡的下界,b[ 2 ]为上界,b[1]无用
T t;
while (change)//如果一趟无交换，则停止
{
change = false;
for ( i=b[1-d]; i!=b[1+d]; i=i+d )//统一的冒泡算法
{
if ( (r[i]-r[i+d])*d > 0 )///注意这个交换条件
{
t = r[i];
r[i] = r[i+d];
r[i+d] = t;
change = true;
}
}
d = d*(-1);//换个方向
}
}
template < typename T >
void SqList<T>::HeapAdjust(int s,int m)
{
/* 已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义，本函数 */
/* 调整H.r[s]的关键字,使H.r[s..m]成为一个大顶堆(对其中记录的关键字而言) */
int j;
T rc = r[s];
for (j=2*s;j <= m;j*=2)
{
/* 沿key较大的孩子结点向下筛选 */
if (j < m && r[j] < r[j+1])
j++;/* j为key较大的记录的下标 */
if (rc >= r[j])
break;/* rc应插入在位置s上 ,无需移动*/
r[s]=r[j];
s=j;
}
r[s]=rc;/* 插入 */
}
template < typename T >
void SqList<T>::HeapSort()
{
/* 对顺序表H进行堆排序。算法10.11 */
T t;
int i;
for (i=length/2;i>0;i--)/* 把H.r[1..H.length]建成大顶堆 */
HeapAdjust(i,length);
for (i=length;i>1;i--)
{
/* 将堆顶记录和当前未经排序子序列H.r[1..i]中最后一个记录相互交换 */
t=r[1];
r[1]=r[i];
r[i]=t;
HeapAdjust(1,i-1);/* 将H.r[1..i-1]重新调整为大顶堆 */
}
}
template < typename T >
void SqList<T>::Build_Heap_Sort()
{
int i;
Build_Heap(length);
for ( i = length; i > 1; i-- )
{
T t;
t = r[i];
r[i] = r[1];
r[1] = t;
Build_Heap(i-1);
}

}
template < typename T >
void SqList<T>::Build_Heap(int len)
{
T t;
for (int i=2; i <= len; i++ )
{
int j = i;
while ( j != 1 )
{
int k = j/2;
if ( r[j] > r[k] )
{
t = r[j];
r[j] = r[k];
r[k] = t;
}
j = k;
}
}

}
template < typename T >
void SqList<T>::Merge(T SR[],T TR[],int i,int m,int n)
{
/* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] 算法10.12 */
int j,k,x;
for (j=m+1,k=i;j<=n&&i<=m;k++)/* 将SR中记录由小到大地并入TR */
{
if (SR[i]<SR[j])
TR[k]=SR[i++];
else
TR[k]=SR[j++];
}
if (i<=m)
for (x=0;x<=m-i;x++)
TR[k+x]=SR[i+x];/* 将剩余的SR[i..m]复制到TR */
if (j<=n)
for (x=0;x<=n-j;x++)
TR[k+x]=SR[j+x];/* 将剩余的SR[j..n]复制到TR */
}
template < typename T >
void SqList<T>::MSort(T SR[],T TR1[],int s,int t)
{
/* 将SR[s..t]归并排序为TR1[s..t]。算法10.13 */
int m;
T *TR2=new T[length+1];
if (s==t)
TR1[s]=SR[s];
else
{
m=(s+t)/2;/* 将SR[s..t]平分为SR[s..m]和SR[m+1..t] */
MSort(SR,TR2,s,m);/* 递归地将SR[s..m]归并为有序的TR2[s..m] */
MSort(SR,TR2,m+1,t);/* 递归地将SR[m+1..t]归并为有序的TR2[m+1..t] */
Merge(TR2,TR1,s,m,t);/* 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t] */
}
}
template < typename T >
void SqList<T>::MergeSort()
{
MSort(r,r,1,length);
}
template < typename T >
void SqList<T>::OE_Sort()
{
int i;
T t;
bool change = true;
while ( change )
{
change = false;
for ( i=1;i<length;i+=2 )
{
if (r[i] > r[i+1])
{
t = r[i];
r[i] = r[i+1];
r[i+1] = t;
change = true;
}
}
for ( i=2;i<length;i+=2 )
{
if ( r[i] > r[i+1] )
{
t = r[i];
r[i] = r[i+1];
r[i+1] = t;
change = true;
}
}

}

}
typedef struct
{
int low;
int high;
}boundary;
template <typename T >
void SqList<T>::Q_Sort_NotRecurre()
{
int low=1,high=length;
int piv;
boundary bo1,bo2;
stack<boundary> st;
while (low < high)
{
piv = Partition(low,high);
if ( (piv-low < high-piv) && (high-piv > 2) )
{
bo1.low = piv+1;
bo1.high = high;
st.push(bo1);
high = piv-1;
}
else if ( (piv-low > high-piv) && (piv-low >2) )
{
bo1.low = low;
bo1.high = piv-1;
st.push(bo1);
low = piv+1;
}
else
{
Easy_Sort(low,high);
high = low;
}
}
while ( !st.empty() )
{
bo2 = st.top();
st.pop();
low = bo2.low;
high = bo2.high;
piv = Partition(low, high);
if ( (piv-low < high-piv) && (high-piv > 2) )
{
bo1.low = piv+1;
bo1.high = high;
st.push(bo1);
high = piv-1;
}
else if ( (piv-low > high-piv) && (piv-low >2) )
{
bo1.low = low;
bo1.high = piv-1;
st.push(bo1);
low = piv+1;
}
else
{
Easy_Sort(low,high);
}
}

}
template < typename T >
void SqList<T>::Easy_Sort(int low,int high)
{
T t;
if ( (high-low) == 1 )
{
if ( r[low] > r[high] )
{
t = r[low];
r[low] = r[high];
r[high] = t;
}
}
else
{
if ( r[low] > r[low+1] )
{
t = r[low];
r[low] = r[low+1];
r[low+1] = t;
}
if ( r[low+1] > r[high] )
{
t = r[low+1];
r[low+1] = r[high];
r[high] = t;
}
if ( r[low] > r[low+1] )
{
t = r[low];
r[low] = r[low+1];
r[low+1] = t;
}
}

}

template < typename T >
void SqList<T>::HeapAdjust_3(int s,int m)
{
T rc = r[s];
for (int j = 3*s-1; j <= m;j=j*3-1)
{
if (j+1<m)//有3个孩子结点
{
if ( rc>=r[j] && rc>=r[j+1] && rc>=r[j+2] )
break;
else
{
if ( r[j] > r[j+1] )
{
if ( r[j] > r[j+2] )
{
r[s]=r[j];
s=j;
}
else//r[j]<=r[j+2]
{
r[s]=r[j+2];
s=j+2;
}
}
else//r[j]<=r[j+1]
{
if ( r[j+1] > r[j+2] )
{
r[s]=r[j+1];
s=j+1;
}
else//r[j+1]<=r[j+2]
{
r[s]=r[j+2];
s=j+2;
}
}
}
}
if ( j+1==m )//有2个孩子结点
{
if ( rc>=r[j] && rc>=r[j+1] )
break;
else
{
if ( r[j] > r[j+1] )
{
r[s]=r[j];
s=j;
}
else//r[j]<=r[j+1]
{
r[s]=r[j+1];
s=j+1;
}
}
}
if (j==m)//有1个孩子结点
{
if ( rc>=r[j] )
break;
else
{
r[s]=r[j];
s=j;
}
}
}
r[s]=rc;
}

template <typename T >
void SqList<T>::HeapSort_3()
{
int i;
T t;
for (i=length/3; i>0; i--)
HeapAdjust_3(i,length);
for ( i=length; i > 1; i-- )
{
t = r[i];
r[i] = r[1];
r[1] = t;
HeapAdjust_3(1,i-1);
}
}

int _tmain(int argc, _TCHAR* argv[])
{
SqList<int> Sq(15);
//Sq.InsertSort();
//Sq.BInsertSort();
/* 希尔排序*/
// int a[5]={5,4,3,2,1};
// Sq.ShellSort(a,5);

/* Sq.QuickSort();*/

// Sq.SelectSort();

/* Sq.BubbleSort();*/

/* Sq.HeapSort();*/

/* Sq.MergeSort();*/

/* Sq.Q_Sort_NotRecurre();*/

/* Sq.Bubble_Sort2();*/
/* Sq.OE_Sort();*/
/* Sq.Bubble_Sort3();*/

/* Sq.Build_Heap_Sort();*/

Sq.HeapSort_3();

Sq.DisPlay();
system("pause");
return 1;
}

㈡ 算法如何刷题

1、原题
我自己感觉原题的概率还是挺大的，特别是剑指offer的66题更是如此。千万别小看这66题，这几十道题里面基本所有的算法类型都有包括在内，常用的数据结构，操作方式，常用算法思路都有不少的题。

如果真的能够充分理解这几十道题的最优解，我感觉其实已经形成基本的算法思维了。

另外，leetcode的原题也很常见，因为LC本身题量大，在里面出原题不是为了考倒你，而是检验你的刷题质量。

毕竟那些大公司面试官也不是傻子，知道你在面试前肯定会大规模刷题的。所以把刷过的题完全搞懂才是最重要的。

2、改编题
改编题就很显而易见了。改编题大多需要从基本的算法原理中找到处理的思维，然后结合实际题干进行性能优化，就能够搞定。

这里要记得一点的是，正常的算法考察不会故意刁难你（正常情况），也不会给过多的时间让你思考和敲代码。

所以遇到改编题不要想得太复杂，尽量要找到它的算法思维是什么。怎么说呢，透过现象看本质。我总结的改编题有以下几种思路：

1）新的数据结构，换汤不换药。比如最常见的排序算法的改编，原来是对数字进行排序，现在对链表排序等等。比较难一点的可能会遇到自定义的数据结构。但是算法本质不会变。

2）算法类型改编。

这里要说的就是一个比较大的范围，比如动态规划、贪心算法、递归、回溯和分治等等。这种是从算法大的类型上进行改编，很难用相同的套路去解题。

遇到这类题的关键就是要先弄明白算法核心。比如动态规划的状态方程，贪心算法的局部最优情况，递归回溯的边界判断，分治的子问题划分等等。这种类型的确比较难把握，怎么硕呢，每种类型的都来搞几道感觉感觉吧。

3）添加应用题背景。

这种题目看起来不难，但是难就难在对应用题背景的理解，需要去理解题意，然后考虑合适的数据结构和处理算法。这里面有数学建模的思维在里面，需要把一堆无用的信息剔除，筛选出有效的信息，然后才能选择正确的算法。

3、创新题
这类题考察的是你的扩展思维，如果说上面的题考查的是你的思维深度，这种题就是考察算法的广度。可能一看题目，完全没见过这种类型。但是算法本身其实不就是让计算机代替人脑进行高重复性的计算嘛。

首先你需要想到你应该去怎么算这个题，然后再换到计算机上，会发生什么问题（空间时间问题，运行效率，代码冗余等等），之后再想通过经典的算法原理来解决这些

1、题型分类
按照个人的习惯，喜欢按照一种类型狂刷，然后再刷另外一种类型。一般常见的算法类型可分为：

数组、链表

包含基本排序算法、二分查找、链表的一系列操作。

栈、队列、堆

利用栈、队列互相实现，堆的使用

二叉树与图

主要是遍历算法和节点的计算：
二叉树四种遍历方式、广度优先遍历（BFS）和广度优先遍历（DFS），节点到节点距离等等。

哈希表

使用标准库自带的模板或者函数就很简单了，一般会与其它数据结构相结合来提升时间复杂度。

字符串操作

字符串的操作也很多，本质上可以看作是数组的操作。另外字符串的一些匹配和寻求字串的算法还是非常具有思考价值的。KMP，马拉车等等。

递归

重点掌握边界判断条件。

回溯

重点掌握边界判断条件。

分治

重点掌握如何划分子问题。

动态规划

题太多了，可从一阶dp到二阶dp理解不同的状态方程。

贪心及其它

这个就很容易理解了，遇到贪心题应该要偷笑了。

2、高频热点多刷
这不多说了吧，Leetcode热题HOT 100。你值得拥有。

在不知道怎么刷的情况下，不如先刷起来。刷个题没那么多捷径，只有坚持刷起来了，才会形成自己的思维方式和学习习惯。

我建议是先按照类型刷，每个类型刷十几二十道。然后打混按照算法热度排序重新查漏补缺。

3、思路回顾
许多同学在一股脑刷了很多题之后，再看做过的题会发现忘了不少。可能大家都是这样的吧。我觉得是因为在刷题的时候过于心急，理解了大概就过了，或者类型做的太杂，没有留下印象。

我比较喜欢的方式是偶尔会重新看看曾经做过的题，就看题目然后想思路，再画一画步骤演进，没时间就不细敲了。这样可以增强一下思维记忆，之前理解过的东西，再回忆起来还是非常快的。

㈢ 用c语言写一个数组从小到大输出

这是一种最原始的排序算法，比较接近于选择排序，即每次选出一个最小的元素放到a[i]的位置，然后对a[i+1]~a[9]的元素再重复上述操作，直到完成整个排序过程。但是这个排序算法做了很多无用的交换操作，浪费了很多时间。对这个循环过程进行改进可以变成标准的选择排序或是冒泡排序。

㈣ [在线等]冒泡排序算法的一些疑问（C语言） #include <stdio.h

一 先说简单的,最后的Return 1
1,为什么需要Return ,因为是int main() 是有返回值的函数
2, Return后面应该写多少.这分两情况,如果有其它地方对你的返回值有兴趣,你就要按约定的意义来写,如果没有任何地方对你的返回值有兴趣,那你写几都可以.

二 再说说那个flag
1,这里为什么要加这个标志位呢?
程序的设计思想是好的,通过增加这个标志位,已减少不必要的计算.看个例子:
如果你输入:2 1 3 4 5 6 7 8 9 10 这时候,我们只需要改变2和1的位置,就排好序了.你现在的代码是按从小到大排序,冒泡排序就是每次循环中在剩余数中找到最小的那个放到对应的位置.
如果没有flag这个变量,在第一次循环中,把1放到了最前面,程序还会去接着循环8次,对后面的数进行排序,这其实就是无用操作,因为后面的已经排好序了.
2,flag起到这个作用了吗?
没有,因为代码写的有问题,没有达到这个目标,以现在的代码,只有输入的数是:1 2 3 4 5 6 7 8 9 10
才会执行到break这里,跳出循环:
if(flag==1)
{
break;
}
而对:2 1 3 4 5 6 7 8 9 10这种输入就没有作用了,因为在第一次循环中,它就把flag的值改成0了,它永远也不会==1,所以代码要改成这样
if(flag==1)
{
break;
}
flag = 1;

好,就这么多了,其它你自己想去吧

㈤ 谁帮我写一份c语言版的各种排序算法的效率比较

（1）“冒泡法” 冒泡法大家都较熟悉。其原理为从a[0]开始，依次将其和后面的元素比较,若a[0]>a[i]，则交换它们，一直比较到a[n]。同理对a[1],a[2],...a[n-1]处理，即完成排序。下面列出其代码：void bubble(int *a,int n) /*定义两个参数：数组首地址与数组大小*/ { int i,j,temp; for(i=0;i<n-1;i++) for(j=i+1;j<n;j++) /*注意循环的上下限*/ if(a[i]>a[j]) { temp=a[i]; a[i]=a[j]; a[j]=temp; } } 冒泡法原理简单，但其缺点是交换次数多，效率低。 下面介绍一种源自冒泡法但更有效率的方法“选择法”。 （2）“选择法” 选择法循环过程与冒泡法一致，它还定义了记号k=i,然后依次把a[k]同后面元素比较，若a[k]>a[j],则使k=j.最后看看k=i是否还成立，不成立则交换a[k],a[i],这样就比冒泡法省下许多无用的交换，提高了效率。void choise(int *a,int n) { int i,j,k,temp; for(i=0;i<n-1;i++) { k=i; /*给记号赋值*/ for(j=i+1;j<n;j++) if(a[k]>a[j]) k=j; /*是k总是指向最小元素*/ if(i!=k) { /*当k!=i是才交换，否则a[i]即为最小*/ temp=a[i]; a[i]=a[k]; a[k]=temp; } } } 选择法比冒泡法效率更高，但说到高效率，非“快速法”莫属，现在就让我们来了解它。 （3）“快速法” 快速法定义了三个参数，（数组首地址*a,要排序数组起始元素下标i,要排序数组结束元素下标j). 它首先选一个数组元素（一般为a[(i+j)/2],即中间元素）作为参照，把比它小的元素放到它的左边，比它大的放在右边。然后运用递归，在将它左，右两个子数组排序，最后完成整个数组的排序。下面分析其代码：void quick(int *a,int i,int j) { int m,n,temp; int k; m=i; n=j; k=a[(i+j)/2]; /*选取的参照*/ do { while(a[m]<k&&m<j) m++; /* 从左到右找比k大的元素*/ while(a[n]>k&&n>i) n--; /* 从右到左找比k小的元素*/ if(m<=n) { /*若找到且满足条件，则交换*/ temp=a[m]; a[m]=a[n]; a[n]=temp; m++; n--; } }while(m<=n); if(m<j) quick(a,m,j); /*运用递归*/ if(n>i) quick(a,i,n); } （4）“插入法” 插入法是一种比较直观的排序方法。它首先把数组头两个元素排好序，再依次把后面的元素插入适当的位置。把数组元素插完也就完成了排序。void insert(int *a,int n) { int i,j,temp; for(i=1;i<n;i++) { temp=a[i]; /*temp为要插入的元素*/ j=i-1; while(j>=0&&temp<a[j]) { /*从a[i-1]开始找比a[i]小的数，同时把数组元素向后移*/ a[j+1]=a[j]; j--; } a[j+1]=temp; /*插入*/ } } （5）“shell法” shell法是一个叫 shell 的美国人与1969年发明的。它首先把相距k(k>=1)的那几个元素排好序，再缩小k值（一般取其一半），再排序，直到k=1时完成排序。下面让我们来分析其代码：void shell(int *a,int n) { int i,j,k,x; k=n/2; /*间距值*/ while(k>=1) { for(i=k;i<n;i++) { x=a[i]; j=i-k; while(j>=0&&x<a[j]) { a[j+k]=a[j]; j-=k; } a[j+k]=x; } k/=2; /*缩小间距值*/ } } 上面我们已经对几种排序法作了介绍，现在让我们写个主函数检验一下。 #include<stdio.h> /*别偷懒，下面的"..."代表函数体，自己加上去哦！*/ void bubble(int *a,int n) { ... } void choise(int *a,int n) { ... } void quick(int *a,int i,int j) { ... } void insert(int *a,int n) { ... } void shell(int *a,int n) { ... } /*为了打印方便，我们写一个print吧。*/[code]void print(int *a,int n) { int i; for(i=0;i<n;i++) printf("%5d",a[i]); printf("\n"); } main() { /*为了公平，我们给每个函数定义一个相同数组*/ int a1[]={13,0,5,8,1,7,21,50,9,2}; int a2[]={13,0,5,8,1,7,21,50,9,2}; int a3[]={13,0,5,8,1,7,21,50,9,2}; int a4[]={13,0,5,8,1,7,21,50,9,2}; int a5[]={13,0,5,8,1,7,21,50,9,2}; printf("the original list:"); print(a1,10); printf("according to bubble:"); bubble(a1,10); print(a1,10); printf("according to choise:"); choise(a2,10); print(a2,10); printf("according to quick:"); quick(a3,0,9); print(a3,10); printf("according to insert:"); insert(a4,10); print(a4,10); printf("according to shell:"); shell(a5,10); print(a5,10); }

㈥ 请给我详细解释一下这段程序 谢谢了！！！C语言的！

这是一个数组的冒泡排序算法。
void fun(int bb[], int n)
{
int i, j, t;//i,j作为数组下标变量,t用于交换两个数时的临时变量
for (i=0; i<n; i++)
for (j=0; j<n-1; j++)
if (bb[j] > bb[j+1])//比较两个数,如果第一个数大于第二个数，则交换它们
{
t = bb[j];//这三行是交换两个数
bb[j] = bb[j+1];
bb[j+1] = t;
}
}
冒泡算法顾名思义，就是让最小的数一点一点被换到最前面来，当然如果比较的时候if (bb[j] > bb[j+1])这里用的是小于，那就是小的一点点被交换到后面去。
程序开始的时候首先让数组的第一个数和第二个数比较，如果第一个数较大，则交换它们，以此类推，把最大的一个数交换到最后，然后再找前面剩下的最大数放到倒数第二个位置，如此循环下去，直到循环完成，数组也就排序完成了。

对问题补充的回答：
楼主的这个算法还可以再优化一下，比如该数组一开始是：
5,2,4,8,9,7这样，
第一次内部循环开始，
j=0,5>2成立,所以交换，变成
2,5,4,8,9,7
j=1,5>4成立,所以交换，变成
2,4,5,8,9,7
j=2,5>8不成立，所以不用交换
2,4,5,8,9,7
j=3,8>9不成立，所以不用交换
2,4,5,8,9,7
j=4,9>7成立，所以交换，变成
2,4,5,8,7,9
第一次循环结束，把最大的9换到了最后。接下来还要依次找出第二大的，第三大的。。直到5次后，最终变成：
2,4,5,7,8,9，这就是第一个循环for (i=0; i<n; i++)的作用，因为一次内部循环只能把最大的第一个数交换到最后去，但是前面的还没有完成排序，所以总共需要数组个数的次数才能确保交换完毕。
其实上面这个数组还可以看出，外层循环只要运行两次，也就是当i=2的时候，数组就已经是按从小大大排列好了，所以，它有很多的时间都在做无用功。不管给定的数组是什么样的顺序，它都要做完双重循环，其实我们完全可以在程序中增加判断，如果内部循环一次下来，没有发生过交换，就说明，数组已经是排序好了，这时候就可以终止程序了，这样可以提高程序的效率，以下是优化过的冒泡排序算法：

#define bool int
#define false 0
#define true 1
void funSort(int aa[],int n)
{
int iCount=0;//用来记录排序所用次 数
int i,j,t;//i,j为数组下标变量，t为交换临时变量
bool bChange;//用来记录内层循环是否发生过交换，如果没有发生过交换，则说明数组已经是有序的，就可以终止排序了。
for(i=0;i<n;i++)//总共需要n次外层循环
{
bChange=false;//初值为false,没有发生过交换
for(j=n-1;j>0;j--)//从后往前比较，把最小的交换到前面去，就像气泡一样，冒到最上面。
{
iCount++;//循环计数器加1
if(aa[j]<aa[j-1])
{
bChange=true;//发生过交换，则继续比较
t=aa[j];//以下三行交换两个数
aa[j]=aa[j-1];
aa[j-1]=t;
}
}
if(!bChange) break;//如果没有发生过交换，则终止排序
}
printf("排序比较总次数:%d\n",iCount);//显示排序所用的次数
}

楼主可以自己在电脑上试一下，先输入一个已经排序好的数组(最好情况)，看看排序总共进行了多少次比较，再输入一个逆序的数组(最坏情况)，再看看进行了多少次比较.
还有不明白的，再交流，呵呵。可以发网络H消息给我。

㈦ 如何在现代C中实现经典排序算法

冒泡法大家都较熟悉。其原理为从a[0]开始，依次将其和后面的元素比较,若a[0]>a[i]，则交换它们，一直比较到a[n]。同理对a[1],a[2],...a[n-1]处理，即完成排序。下面列出其代码：
void bubble(int *a,int n) /*定义两个参数：数组首地址与数组大小*/
{
int i,j,temp;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++) /*注意循环的上下限*/
if(a[i]>a[j]) {
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
冒泡法原理简单，但其缺点是交换次数多，效率低。
下面介绍一种源自冒泡法但更有效率的方法“选择法”。
（2）“选择法”
选择法循环过程与冒泡法一致，它还定义了记号k=i,然后依次把a[k]同后面元素比较，若a[k]>a[j],则使k=j.最后看看k=i是否还成立，不成立则交换a[k],a[i],这样就比冒泡法省下许多无用的交换，提高了效率。
void choise(int *a,int n)
{
int i,j,k,temp;
for(i=0;i<n-1;i++) {
k=i; /*给记号赋值*/
for(j=i+1;j<n;j++)
if(a[k]>a[j]) k=j; /*是k总是指向最小元素*/
if(i!=k) { /*当k!=i是才交换，否则a[i]即为最小*/
temp=a[i];
a[i]=a[k];
a[k]=temp;
}
}
}
选择法比冒泡法效率更高，但说到高效率，非“快速法”莫属，现在就让我们来了解它。
（3）“快速法”
快速法定义了三个参数，（数组首地址*a,要排序数组起始元素下标i,要排序数组结束元素下标j). 它首先选一个数组元素（一般为a[(i+j)/2],即中间元素）作为参照，把比它小的元素放到它的左边，比它大的放在右边。然后运用递归，在将它左，右两个子数组排序，最后完成整个数组的排序。下面分析其代码：
void quick(int *a,int i,int j)
{
int m,n,temp;
int k;
m=i;
n=j;
k=a[(i+j)/2]; /*选取的参照*/
do {
while(a[m]<k&&m<j) m++; /* 从左到右找比k大的元素*/
while(a[n]>k&&n>i) n--; /* 从右到左找比k小的元素*/
if(m<=n) { /*若找到且满足条件，则交换*/
temp=a[m];
a[m]=a[n];
a[n]=temp;
m++;
n--;
}
}while(m<=n);
if(m<j) quick(a,m,j); /*运用递归*/
if(n>i) quick(a,i,n);
}
（4）“插入法”
插入法是一种比较直观的排序方法。它首先把数组头两个元素排好序，再依次把后面的元素插入适当的位置。把数组元素插完也就完成了排序。
void insert(int *a,int n)
{
int i,j,temp;
for(i=1;i<n;i++) {
temp=a[i]; /*temp为要插入的元素*/
j=i-1;
while(j>=0&&temp<a[j]) { /*从a[i-1]开始找比a[i]小的数，同时把数组元素向后移*/
a[j+1]=a[j];
j--;
}
a[j+1]=temp; /*插入*/
}
}
（5）“shell法”
shell法是一个叫 shell 的美国人与1969年发明的。它首先把相距k(k>=1)的那几个元素排好序，再缩小k值（一般取其一半），再排序，直到k=1时完成排序。下面让我们来分析其代码：
void shell(int *a,int n)
{
int i,j,k,x;
k=n/2; /*间距值*/
while(k>=1) {
for(i=k;i<n;i++) {
x=a[i];
j=i-k;
while(j>=0&&x<a[j]) {
a[j+k]=a[j];
j-=k;
}
a[j+k]=x;
}
k/=2; /*缩小间距值*/
}
}
上面我们已经对几种排序法作了介绍，现在让我们写个主函数检验一下。
#include<stdio.h>
/*别偷懒，下面的"..."代表函数体，自己加上去哦！*/
void bubble(int *a,int n)
{
...
}
void choise(int *a,int n)
{
...
}
void quick(int *a,int i,int j)
{
...
}
void insert(int *a,int n)
{
...
}
void shell(int *a,int n)
{
...
}
/*为了打印方便，我们写一个print吧。*/[code]
void print(int *a,int n)
{
int i;
for(i=0;i<n;i++)
printf("%5d",a[i]);
printf("\n");
}
main()
{ /*为了公平，我们给每个函数定义一个相同数组*/
int a1[]={13,0,5,8,1,7,21,50,9,2};
int a2[]={13,0,5,8,1,7,21,50,9,2};
int a3[]={13,0,5,8,1,7,21,50,9,2};
int a4[]={13,0,5,8,1,7,21,50,9,2};
int a5[]={13,0,5,8,1,7,21,50,9,2};
printf("the original list:");
print(a1,10);
printf("according to bubble:");
bubble(a1,10);
print(a1,10);
printf("according to choise:");
choise(a2,10);
print(a2,10);
printf("according to quick:");
quick(a3,0,9);
print(a3,10);
printf("according to insert:");
insert(a4,10);
print(a4,10);
printf("according to shell:");
shell(a5,10);
print(a5,10);
}

㈧ c++基数排序算法的问题

写得很复杂啊！

更改后如下：

#include<iostream>
#include<math.h>
using namespace std;
struct Node{
int data;
Node *prior;
Node *next;
};

void createlinklist(Node* &L){
Node *p;
Node *q;
L=new Node;
L->next=NULL;
L->prior=NULL;

//q=new Node; /* 无用 zhjiemm */

//p = new Node; /* 无用 zhjiemm */
//p->next=NULL; /* 无用 zhjiemm */

int adata=0;
q=L;
while(adata!=-1){
p= new Node;
p->data=adata;
p->prior=NULL;
p->next=NULL;

p->prior=q;
q->next=p;
q=p;
cin>>adata;
if(adata==-1){
L=L->next;
q->next=L;
L->prior=q;

}
}
}
//****************************************************
//子函数
// getNode()
Node* getNode(Node* &L){ /********** 全部改写 ********** zhjiemm */
Node *p;
p=L->next;
if(p!=L){
L->next = p->next;
p->next->prior = L;
}else{
p=NULL;
}
return p;
}
//getNumber()
int getNumber(Node *p,int i){
int pdata,k;
pdata=p->data;
k=(int)(pdata/pow(10,i));
return k%10;
}
//addNode()
void addNode(Node* &lhead,Node *p){
p->prior=lhead->prior;
p->next=lhead;
lhead->prior->next=p;
lhead->prior=p;

}
//append()
void append(Node* &L,Node* lhead){
if(lhead->next != lhead){//不为空
L->prior->next=lhead->next; /********** 指针指错了 ********** zhjiemm */
lhead->next->prior=L->prior;
lhead->prior->next=L;
L->prior=lhead->prior;
}
}
//****************************************************
//基数排序主函数
void radix_sort(Node *&L,int k){
Node *Lhead[10],*p;
int i,j,flag;
cout<<"*****\n";
for(i=0;i<10;i++)
Lhead[i]=new Node;

for(i=0;i<k;i++){//第倒数k(位)轮
for(j=0;j<10;j++)//清空
Lhead[j]->next=Lhead[j]->prior=Lhead[j];

while(L->next!=L){//L中的数放入lhead[n]中
p=getNode(L);
if(p) /********** 判断一下不为空 ********** zhjiemm */
{
flag=getNumber(p,i);//第n轮，取倒数第n位数
addNode(Lhead[flag],p);
}
}
for(int m=0;m<10;m++)//将lhead[n]中的数放入L中
append(L,Lhead[m]);
}

}

int main()
{
Node *L;
createlinklist(L);
radix_sort(L,4);
Node *p=L->next; /* 初始值不对 zhjiemm */
while(p!=L){
cout<<p->data<<" ";
p=p->next;

}

return 0;
}

注：使用完链表后，要记得释放。

㈨ 冒泡排序算法

DATA SEGMENT
NUM DB 32H , 43H , 23H , 54H , 76H , 45H , 24H , 78H ; 自己添加数
N = $ - NUM
DATA ENDS

STACK SEGMENT STACK
DB 200 DUP(0)
STACK ENDS

CODE SEGMENT
ASSUME CS:CODE , DS:DATA , SS:STACK
START :
MOV AX , DATA
MOV DS , AX
LEA BX , NUM
MOV SI , N
CALL SORT
MOV AH , 4CH
INT 21H
; 子程序名: SORT
; 功能：将8位无符号的二进制数按递增顺序排列
; 入口参数：BX---存放待排数组存贮区首址
; 入口参数：SI---存放待排序数的个数
; 出口参数：已排成递增的n个无符号数仍存放在由BX指示首址的字节缓存区中
; 所用寄存器：DI---用来存放n-1，即（SI)-1 , AX --- 用来存放临时数
; 算法：一次找一个最大的然后直接递归
SORT PROC
CMP SI , 1
JG EXECUTE ; 大于一个数就执行排序， 否则直接跳出子程序
RET
EXECUTE :
PUSH AX
PUSH DI
PUSH SI ; 保护现场
MOV DI , SI
LOPA :
DEC DI
CMP DI , 0
JNE COMPARE ; 不相等就继续比较 ....
DEC SI ; 等于0 ， 进行下一轮的调用
CALL SORT ;
POP SI
POP DI
POP AX
RET ; 返回
COMPARE :
MOV AL , [BX+DI-1] ; 第DI个数
CMP AL , [BX+SI-1] ; 第SI个数
JLE LOPA ; 小于不交换
XCHG AL , [BX+SI-1] ; 交换两个数
MOV [BX+DI-1] , AL
JMP LOPA
SORT ENDP
CODE ENDS
END START

㈩ 一个关于C语言数组排序的问题

#include<stdio.h>
/**排序无用、逻辑错明显**/
void main()
#define n 5
{
    int a[n],i,j,min;
    printf("请输入数组:");
     for(i=0;i<n;i++)
        scanf("%d",&a[i]);
     //若使用宏n这里有可能会数组越界 根据编译器类型。
    for(i=0;i<sizeof(a)/sizeof(a[0])-1;i++)
    {  //可以参考冒泡排序
       min=a[i];
       for(j=i+1;/*应该是j*/j<sizeof(a)/sizeof(a[0]);j++)//不是i 是j
       {
          if (min>a[j])
            min=a[j];
       }
       a[i]=min;//这里会导致 a[i]=minvalue  forever.
     }
    for(i=0;i<sizeof(a)/sizeof(a[0]);i++)
        printf("%3d
",a[i]);
}

参照一个排序算法来写。网络c冒泡排序。