C语言冒泡排序？

一、C语言冒泡排序？

将被排序的记录数组R[1..n]垂直排列，每个记录R看作是重量为R.key的气泡。

根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。

如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。

二、C语言多项排序？

1、稳定排序和非稳定排序

简单地说就是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就说这种排序方法是稳定的。反之，就是非稳定的。

比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为a1,a2,a4,a3,a5，则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4,a2,a3,a5就不是稳定的了。

2、内排序和外排序

在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序；

在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。

3、算法的时间复杂度和空间复杂度

所谓算法的时间复杂度，是指执行算法所需要的计算工作量。

一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。

二、各类排序算法分析

1、冒泡排序

====================================================

算法思想简单描述：

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

下面是一种改进的冒泡算法，它记录了每一遍扫描后最后下沉数的位置k，这样可以减少外层循环扫描的次数。

冒泡排序是稳定的。算法时间复杂度O(n2)--[n的平方]

=====================================================

＃i nclude <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、选择排序

====================================================

算法思想简单描述：

在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

选择排序是不稳定的。算法复杂度O(n2)--[n的平方]

====================================================

＃i nclude <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)。所以，在数据较乱的时候，可以减少一定的交换次数。

3、直接插入排序

====================================================

算法思想简单描述：

在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

直接插入排序是稳定的。算法时间复杂度O(n2)--[n的平方]

=====================================================

#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->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)（推导类似选择法），但我们每次要进行与内层循环相同次数的‘=’操作。正常的一次交换我们需要三次‘=’ 而这里显然多了一些，所以我们浪费了时间。

个人认为在简单排序算法中，选择法是最好的。

4、希尔排序

====================================================

算法思想简单描述：

在直接插入排序算法中，每次插入一个数，使有序序列只增加1个节点，并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除

多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成

一组，排序完成。

下面的函数是一个希尔排序算法的一个实现，初次取序列的一半为增量，以后每次减半，直到增量为1。

希尔排序是不稳定的。

=====================================================

这个排序非常复杂，看了程序就知道了。 首先需要一个递减的步长，这里我们使用的是9、5、3、1（最后的步长必须是1）。工作原理是首先对相隔9-1个元素的所有内容排序，然后再使用同样的方法对相隔5-1个元素的排序，以次类推。

＃i nclude <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次幂。同样因为非常复杂并 “我也不知道过程"，我们只有结果了。

5、快速排序

====================================================

算法思想简单描述：

快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。它是由C.A.R.Hoare于1962年提出的。

显然快速排序可以用递归实现，当然也可以用栈化解递归实现。下面的函数是用递归实现的，有兴趣的朋友可以改成非递归的。

快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n)，最坏O(n2)

=====================================================

＃i nclude <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)算法，但是通常情况下速度要慢于快速排序（因为要重组堆）。

6、堆排序

====================================================

算法思想简单描述：

堆排序是一种树形选择排序，是对直接选择排序的有效改进。

堆的定义如下：具有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

{

if (j

< *(x+j+1)) *判断是否满足堆的条件：满足就继续下一轮比较，否则调整。* && *(x+j) /> {

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

{

scanf("%d",p++);

}

printf("\n");

p = a;

select_sort(p,MAX);

for (p=a, i=0; i

{

printf("%d ",*p++);

}

printf("\n");

system("pause");

}

其他的交换法，双向冒泡法等等就不具体介绍了。

三、几种排序算法的比较和选择

1. 选取排序方法需要考虑的因素：

(1) 待排序的元素数目n；

(2) 元素本身信息量的大小；

(3) 关键字的结构及其分布情况；

(4) 语言工具的条件，辅助空间的大小等。

四、小结：

(1) 若n较小(n <= 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。

(2) 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。

(3) 若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。快速排序是目前基于比较的内部排序法中被认为是最好的方法。

(4) 在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于"比较"的排序算法，至少需要O(nlog2n)的时间。

(5) 当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构。

三、C语言程序，排序----快速排序法？

快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。

它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小。

然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

扩展：C语言是一门面向过程的、抽象化的通用程序设计语言，广泛应用于底层开发。C语言能以简易的方式编译、处理低级存储器。C语言是仅产生少量的机器语言以及不需要任何运行环境支持便能运行的高效率程序设计语言。尽管C语言提供了许多低级处理的功能，但仍然保持着跨平台的特性，以一个标准规格写出的C语言程序可在包括类似嵌入式处理器以及超级计算机等作业平台的许多计算机平台上进行编译。

四、c语言ASCII码排序？

思路：就是求三个字符按照ASCII码顺序进行排序输出，三个字符排序可以先求出三个数中的最大值和最小值，再把三个字符相加减去最大和最小的就是中间字符。

参考代码：

#include<stdio.h>main(){ char a,b,c,max,min; while(scanf("%c%c%c",&a,&b,&c)!=EOF) { max=(a>b?a:b)>c?(a>b?a:b):c; min=(a<b?a:b)<c?(a<b?a:b):c; printf("%c %c %c\n",min,a+b+c-min-max,max); }}/*输出：qweasdzxce q wa d sc x z*/

五、冒泡排序法c语言？

C语言冒泡排序算法

用冒泡排序法对任意输入的 10 个数按照从小到大的顺序进行排序。实现过程：(1) 通过两个 for 循环实现冒泡排序的全过程，外层 for 循环决定冒泡排序的趟数，内层 for 循环决定每趟所进行两两比较的次数。(2) 程序代码如下：

运行结果：

请输入10个数：66 32 23 45 25 5 15 69 46 37排序后的顺序是： 5 15 23 25 32 37 45 46 66 69

技术要点：

本实例要求用冒泡法对 10 个数由小到大进行排序，冒泡法的基本思路是，如果要对 n 个数进行冒泡排序，那么要进行 n-1 趟比较，在第 1 趟比较中要进行 n-j 次两两比较，在第 j 趟比较中要进行 n-j 次两两比较。从这个基本思路中就会发现，趟数决定了两两比较的次数，这样就很容易将两个 for 循环联系起来了。

六、c语言数组排序讲解？

C语言将数组元素大小排序方法： 以下使用的是冒泡排序法实线数组从小到大排序。 思想：每次相邻两个数比较，若升序，则将大的数放到后面，一次循环过后，就会将最大的数放在最后。

10、2、3、4、5、6、9、8、7、1是输入的待排序的数列，经过第一次排序，将最大的,10放在最后，第二次排序，将剩下的2、3、4、5、6、9、8、7、1进行冒泡，将当前最大的9放在倒数第二的位置，以此类推。 以下是具体代码：

#include

七、c语言标记排序法？

可以先用冒泡排序法。然后标记处对应的下标号。

八、快速排序法c语言？

快速排序是基于分治技术的重要排序算法，排序算法按照元素的值对它们进行划分。

划分是对给定数组中的元素的重新排序，使得A [ s ] A[s]A[s]左边的元素都小于等于A [ s ] A[s]A[s]，而右边A [ s ] A[s]A[s]右边的元素都大于等于A [ s ] A[s]A[s]。

显然，建立了一个划分以后，A [ s ] A[s]A[s]已经位于它在有序数组中的最终结果，接下来我们可以继续对A [ s ] A[s]A[s]前和A [ s ]A[s]A[s]后的子数组分别进行排序(例如，使用同样的方法)。

注意，它和合并排序不同之处在：

在合并排序算法中，将问题划分为两个子问题，是很快的，算法的主要工作在于合并子问题的解；

在快速排序中，算法的主要工作在于划分阶段，而不需要再去合并子问题的解了。

九、C语言数组排序方法？

C语言将数组元素大小排序方法： 以下使用的是冒泡排序法实线数组从小到大排序。 思想：每次相邻两个数比较，若升序，则将大的数放到后面，一次循环过后，就会将最大的数放在最后。

10、2、3、4、5、6、9、8、7、1是输入的待排序的数列，经过第一次排序，将最大的,10放在最后，第二次排序，将剩下的2、3、4、5、6、9、8、7、1进行冒泡，将当前最大的9放在倒数第二的位置，以此类推。 以下是具体代码：

#include

十、c语言插空排序法？

插空排序法（Insertion Sort）是一种简单直观的排序算法。它的基本思想是将数组分为已排序区和未排序区，每次从未排序区选择一个元素，插入到已排序区的适当位置，直到未排序区为空。

具体操作是从第二个元素开始，逐个与已排序区的元素比较，找到合适的位置插入。

插入过程中，如果发现已排序区的元素比当前元素大，则将已排序区的元素后移一位，直到找到合适的位置。

这样，每次插入一个元素后，已排序区的长度增加1，最终完成排序。插空排序法的时间复杂度为O(n^2)，是一种简单但效率较低的排序算法。