Question

选择排序 冒泡排序 C语言

这两种俺分不清，定义也看了很多遍了，但是没找到好的例子，求高手帮忙写两个例子好吗？
C语言的，环境是NetBeans...当然VC++也可以
好的追加分数...跪谢各位大大...

Answer 1

从程序运行需要的时间和储存空间来看，这两个吧，选择排序用的时间较少。我给你举个例子，这是一个比较直观的例子：
有十个数：10,9,8,7,6,5,4,3,2,1 。将他们按从小到大的顺序排成一列，用这两种方法的区别在于如下过程中：
1、 冒泡排序：
外层循环一共进行9次，第一次将10排到最后，这一步要经很9步交换，即将10依次和9,8,7……交换，成为如下顺序：9,8,7,6,5,4,3,2,1,10；接着第二次将9排到倒数第二，这一步要经过8步交换，变成如下顺序：8,7,6,5,4,3,2,1,9,10;同理执行共九大步，即可将它们最终排成1,2,3,4,5,6,7,8,9,10。
从这个过程可以看到，这种方法在这个过程中一共进行了9+8+7+6+5+4+3+2+1=45次比较和交换。
2、 选择排序：
外层也要经过9次大步，但是不用交换45次.首先要假定一个最大量假设是第一个，并用max标记，第一次，将10依次和9,8,7,6,5,4,3,2，1进行比较，但是只是和1进行了一次交换，这时数列成了：1,9,8,7,6,5,4,3,2,10；第二次:将1和9比较，发现9比较大，那么将9暂时定为最大max，再依次和8,7,6,5,4,3,2比较，最后发现9最大，就把9和倒数第二个位置上的2交换，这一大步共进行了两次交换；依次执行下去，后面每大步进行了两次交换，可以看出，一共进行了1+2+2+2+2+2+2+2+1=16次交换，但是也进行了45次比较。
从上面两种可以看出，这两个方法选择排序更高速，但是某些数据可能使得冒泡排序更高速，即交换次数较少，可以看出算法快慢和数据还是有一定关系的。
至于代码，我写了一个选择排序法的，c++环境运行通过：

请将下面代码复制粘贴到程序写入窗口，按下Ctrl+A全选后，按下Alt+F8即可自动对齐格式：

#include<stdio.h>
#include<time.h>/*包含时间函数，以便作为随机数种子*/
#include<stdlib.h>/*包含产生随机数的文件*/
void main()
{
int i,j,temp,max;
int a[10];
srand((unsigned)time(NULL));/*作用是可以每次产生不一样的随机数*/
for(i=0;i<10;i++)
{
a[i]=rand()%51+49;
}
for(i=0;i<10;i++)
{
printf("a[%d]=%2.0d\t\t",i+1,a[i]);/*控制格式*/
}
printf("\n");
for(i=0;i<10;i++)
{
temp =a[10-i];max=10-i;/*设定最大值*/
for(j=0;j<10-i;j++)
{
if(a[j]> temp)
{
temp =a[j];max=j;/*更新最大值*/
}
}
if(max!=10-i)
{
a[max]=a[10-i];a[10-i] = temp;/*不能忘记将找到最大值处用假设最大值补上！*/
}
}
for(i=0;i<10;i++)
{
printf("a[%d]=%d\t\t",i+1,a[i]);
}
}
没有写冒泡法的，相信你也能写了。写了这么久，希望得个辛苦分。
另外有问题随时问。

Answer 2

选择排序：
void select_sort(int a[],int n) //传入数组的要排序的元素个数
{int i,j,min,t;
for(i=0;i<n-1;i++)
{ min=i; //min:当前最小值下标
for(j=i+1;j<n;j++) //扫描余下的部分
if(a[min]>a[j]) //若有其它元素更小，就记录其下标

min=j;

if(min!=i) //保若最小值不在排序区首位，就换到首位

{t=a[min]; a[min]=a[i]; a[i]=t;}
}
}

冒泡排序：
void bubble_sort(int a[], int n) //传入数组的要排序的元素个数
{ int i, j, t;
for (j=0; j<n-1; j++) //n个元素比较n-1轮
for (i= 0; i<n-1-j;i++) //比较相信的两个数
if(a[i]>a[i+1]) //若大小顺序不符，就交换
{t=a[i]; a[i]=a[i+1]; a[i+1]=t;
}

Answer 3

选择排序：

#include <stdio.h>

int main(void)
{
int i,j,k,a[10];
for (i=0;i<10;i++)
scanf("%d",&a[i]);

for (i=0;i<9;i++)
{
k=i;
for (j=i+1;j<10;++j)
if (a[k]>a[j]) k=j;
if (k!=i)
{
j=a[i];
a[i]=a[k];
a[k]=j;
}
}

for (i=0;i<10;++i) printf("%d ",a[i]);
return 0;
}

冒泡排序：

#include <stdio.h>

int main(void)
{
int i,j,k,a[10];
for (i=0;i<10;i++)
scanf("%d",&a[i]);

for (i=0;i<9;i++)
{
for (j=0;j<8-i;++j)
if (a[j]>a[j+1])
{
k=a[j];
a[j]=a[j+1];
a[j+1]=k;
}
}

for (i=0;i<10;++i) printf("%d ",a[i]);
return 0;
}

Answer 4

以前写的，有5种排序，自己研究一下吧。
#include <stdio.h>
#include <malloc.h>
#include <conio.h>
#include <stdlib.h>

#define MAXSIZE 20

typedef int KeyType;
typedef char InfoType;

typedef struct
{
KeyType key;
InfoType data;

}RedType;

typedef struct
{
RedType r[MAXSIZE + 1];
int length;

}SqList;

//折半插入排序
void BInsertSort(SqList &L)
{
int i, j, low, high, m;
for(i = 2;i <= L.length; i++)
{
L.r[0] = L.r[i];
low = 1;
high = i - 1;
while(low <= high)
{
m=(low + high) / 2;
if(L.r[0].key < L.r[m].key)
high = m - 1;
else
low = m + 1;

}
for(j = i - 1; j >= high + 1; j--)
L.r[j + 1] = L.r[j];
L.r[high + 1] = L.r[0];
for(int k = 1; k <= L.length; k++)
printf("%2d", L.r[k].key);
printf("\n");
}

}
//冒泡排序
void BubbleSort(SqList &L)
{
int i, j, k, n;
RedType temp;
n=L.length;
for(i = 1; i <= n - 1; i++)
{
for(j = n; j > i; j--)
if(L.r[j].key < L.r[j-1].key)
{
temp = L.r[j];
L.r[j] = L.r[j - 1];
L.r[j - 1]=temp;

}
for(k = 1;k <= L.length; k++)
printf("%2d",L.r[k].key);
printf("\n");
}
}
//快速排序
void QuickSort(SqList &L, int s, int t)
{
int i = s, j = t, k;
RedType temp;

if(s < t)
{
temp = L.r[s];
while(i != j)
{
while(j > i && L.r[j].key >= temp.key)
j--;
if(i < j)
{
L.r[i] = L.r[j];
i++;
}
while(j > i && L.r[i].key <= temp.key)
i++;
if(i < j)
{
L.r[j] = L.r[i];
j--;
}
}
L.r[i] = temp;
for(k = 1; k <= L.length; k++)
printf("%2d", L.r[k].key);
printf("\n");
QuickSort(L, s, i - 1);
QuickSort(L, i + 1, t);
}

}
//简单选择排序
int SelectMinkey(SqList &L, int i)
{
int k = L.r[i].key;
int count = i;
for(int j = i; j <= L.length; j++)
{
if (k < L.r[j].key)
{

}
else
{
count = j;
k = L.r[j].key;
}
}
return count;
}

void SelectSort(SqList &L)
{
int i,j;
RedType temp;
for(i = 1; i < L.length; ++i)
{
j = SelectMinkey(L, i);
if(i != j)
{
temp = L.r[i];
L.r[i] = L.r[j];
L.r[j] = temp;

}
for(int k = 1; k <= L.length; k++)
printf("%2d", L.r[k].key);
printf("\n");
}
}
//归并排序
void Merge(RedType r[], int low, int mid, int high) //将2个有序表归并为1个有序表
{
RedType *r1;
int i = low, j = mid + 1, k = 0; //k是r1的下标，i,j分别为第一段和第二段的下标
r1 = (RedType *)malloc((high - low + 1)*sizeof(RedType));
while(i <= mid && j <= high)//在第一段和第二段都没扫描完时循环
if(r[i].key <= r[j].key) //将第一段中的记录放入r1中
{
r1[k] = r[i];
i++;
k++;
}
else //将第二段中的记录放到r1中
{
r1[k] = r[j];
j++;
k++;
}

while(i <= mid) //将第一段剩余部分复制到r1
{
r1[k] = r[i];
i++;
k++;
}
while(j <= high) //将第二段剩余部分复制到r1中
{
r1[k] = r[j];
j++;
k++;
}
for(k = 0, i = low; i <= high; k++,i++) //将r1复制回r中
r[i] = r1[k];

}

void MergePass(RedType r[], int length, int n) //实现一趟归并
{
int i;
for(i = 0; i + 2 * length - 1 < n;i = i + 2 * length) //归并length长的两个相邻子表
Merge(r, i, i + length - 1, i + 2 * length - 1);
if(i + length - 1 < n) //余下2个子表，后者长度小于length
Merge(r, i, i + length - 1, n - 1); //归并这2个表

}

void MergeSort(RedType r[], int n) //二路归并排序
{
int length, k, i = 1;//i用于累计归并趟数
for(length = 1; length < n; length = 2 * length)
{
MergePass(r, length, n);
printf("第%d趟归并:\n",i++);
for(k = 0; k < n; k++)
printf("%2d", r[k].key);
printf("\n");
}
}
//堆排序
void DispHeap(RedType r[],int i,int n)
{
if(i <= n)
printf("%d", r[i].key); //输出根结点
if(2 * i <= n || 2 * i + 1 < n)
{
printf("(");
if(2 * i <= n)
DispHeap(r, 2 * i, n); //递归调用输出左子树
printf(",");
if(2 * i + 1 <= n)
DispHeap(r, 2 * i + 1, n); //递归调用输出右子树
printf(")");
}
}

void Shift(RedType r[], int low, int high) //调整堆
{
int i = low, j = 2 * i; //r[j]是r[i]的左孩子
RedType temp = r[i];
while(j <= high)
{
if(j < high && r[j].key < r[j + 1].key) //若右孩子大，把j指向右孩子
j++; //变为2i+1
if(temp.key < r[j].key)
{
r[i] = r[j]; //将r[i]调整到双亲结点位置
i = j; //修改i,j，以便继续向下筛选
j = 2 * i;
}
else break;
}
r[i] = temp;
}

void HeapSort(RedType r[], int n) //堆排序
{
int i;
RedType temp;
for(i = n / 2; i >= 1; i--) //循环建立初始堆
Shift(r, i, n);
printf("初始堆:\n");
DispHeap(r, 1, n); //输出初始堆
printf("\n");

for(i = n; i >= 2; i--) //进行n-1次循环，完成堆排序
{
printf("交换%d与%d，输出%d\n",r[i].key, r[1].key, r[1].key);
temp = r[1]; //将第一个元素与当前区间内r[1]对换
r[1] = r[i];
r[i] = temp;
Shift(r, 1, i - 1); //筛选r[1]结点，得到i-1个结点的堆
printf("筛选调整得到堆:");
DispHeap(r, 1, i - 1);
printf("\n"); //输出每一趟的排序结果
}

}

void main()
{
SqList L;
L.length = 10;
KeyType a[] = {9,8,7,6,5,4,3,2,1,0};
RedType r[MAXSIZE];
int i, j, k, choice;
printf("常见排序方法演示\n");
printf("1、折半插入排序\n2、冒泡排序\n3、快速排序\n4、简单选择排序\n5、归并排序\n6、堆排序\n0、退出\n");
while(true)
{
scanf("%d", &choice);
for(i = 1; i <= L.length; i++)
L.r[i].key = a[i - 1];
printf("初始关键字为： ");
switch(choice)
{
case 1:
for(j = 1; j <= L.length; j++)
printf("%2d", L.r[j].key);
printf("\n");
BInsertSort(L);
printf("折半排序后为:\n");
break;
case 2:
for(j = 1; j <= L.length; j++)
printf("%2d", L.r[j].key);
printf("\n");
BubbleSort(L);
printf("冒泡排序后为:\n");
break;
case 3:
for(j = 1; j <= L.length; j++)
printf("%2d", L.r[j].key);
printf("\n");
QuickSort(L,1,10);
printf("快速排序后为\n");
break;
case 4:
for(j = 1; j <= L.length; j++)
printf("%2d", L.r[j].key);
printf("\n");
SelectSort(L);
printf("简单选择排序:\n");
break;
case 5:
for(i = 0; i < L.length; i++)
r[i].key = a[i];
for(j = 1; j <= L.length; j++)
printf("%2d", L.r[j].key);
printf("\n");
MergeSort(r, L.length);
printf("归并排序后为\n");
break;
case 6:
for(i = 1; i <= L.length; i++)
r[i].key=a[i - 1];
for(j = 1; j <= L.length; j++)
printf("%2d", L.r[j].key);
printf("\n");
for(i = L.length / 2; i >= 1; i--)
Shift(r, i, L.length);
HeapSort(r, L.length);
printf("堆排序后为:\n");
break;
case 0:
exit(0);
break;
default:
printf("选择有误请重新选择！\n");
break;
}
for(k = 1; k <= L.length; k++)
printf("%2d", L.r[k].key);
printf("\n");
}

}