急求用C语言写的 直插排序,直接选择排序,冒泡排序算法
算法思想到处都可以找到,程序代码还是得自己去写,自己亲手尝试过,才更理解其中的原理。
C和C++差别不大,算法是相同的。
加油吧!
选择法的算法: 假设需要对10个数进行排序,那么首先找出10个数里面的最小数,并和这个10个数的第一个(下标0)交换位置,剩下9个数(这9个数都比刚才选出来那个数大),再选出这9个数中的最小的数,和第二个位置的数(下标1)交换,于是还剩8个数(这8个数都比刚才选出来的大).. 依次类推,当还剩两个数时,选出两个数的最小者放在第9个位置(下标8),于是就只剩下一个数了。这个数已经在最后一位(下标9),不用再选择了。所以10个数排序,一共需要选择9次(n个数排序就需要选择n-1次)。#include "Stdio.h"void main(){ void sa(int array[],int n); int array[10],i; printf("enter the array:
"); for(i=0;i<10;i++) scanf("%d",&array[i]); sa(array,10); printf("the sorted array:
"); for(i=0;i<10;i++) printf("%d",array[i]); getch();}void sa(int array[],int n){ int i,j,k,temp; for(i=0;i<10;i++) { k=i; for(j=i+1;j<n;j++) if(array[j]<array[k]) k=j; temp=array[k]; array[k]=array[i]; array[i]=temp; }}
main() { int i,j,temp; int a[10]; for(i=0;ia[i+1]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp;} } for(i=1;i=i;j--) //对当前无序区R[i..n]自下向上扫描 if(R[j+1].key<R[j].key){//交换记录 R[0]=R[j+1]; //R[0]不是哨兵,仅做暂存单元 R[j+1]=R[j]; R[j]=R[0]; exchange=TRUE; //发生了交换,故将交换标志置为真 } if(!exchange) //本趟排序未发生交换,提前终止算法 return; } //endfor(外循环) } //BubbleSort 4、算法分析 (1)算法的最好时间复杂度 若文件的初始状态是正序的,一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值: Cmin=n-1 Mmin=0。 冒泡排序最好的时间复杂度为O(n)。 (2)算法的最坏时间复杂度 若初始文件是反序的,需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值: Cmax=n(n-1)/2=O(n2) Mmax=3n(n-1)/2=O(n2) 冒泡排序的最坏时间复杂度为O(n2)。 (3)算法的平均时间复杂度为O(n2) 虽然冒泡排序不一定要进行n-1趟,但由于它的记录移动次数较多,故平均时间性能比直接插入排序要差得多。 (4)算法稳定性 冒泡排序是就地排序,且它是稳定的。 5、算法改进 上述的冒泡排序还可做如下的改进: (1)记住最后一次交换发生位置lastExchange的冒泡排序 在每趟扫描中,记住最后一次交换发生的位置lastExchange,(该位置之前的相邻记录均已有序)。下一趟排序开始时,R[1..lastExchange-1]是有序区,R[lastExchange..n]是无序区。这样,一趟排序可能使当前有序区扩充多个记录,从而减少排序的趟数。具体算法【参见习题】。 (2) 改变扫描方向的冒泡排序 ①冒泡排序的不对称性 能一趟扫描完成排序的情况: 只有最轻的气泡位于R[n]的位置,其余的气泡均已排好序,那么也只需一趟扫描就可以完成排序。 【例】对初始关键字序列12,18,42,44,45,67,94,10就仅需一趟扫描。 需要n-1趟扫描完成排序情况: 当只有最重的气泡位于R[1]的位置,其余的气泡均已排好序时,则仍需做n-1趟扫描才能完成排序。 【例】对初始关键字序列:94,10,12,18,42,44,45,67就需七趟扫描。 ②造成不对称性的原因 每趟扫描仅能使最重气泡"下沉"一个位置,因此使位于顶端的最重气泡下沉到底部时,需做n-1趟扫描。 ③改进不对称性的方法 在排序过程中交替改变扫描方向,可改进不对称性。
勤奋一点网上都可找到,这是帮你拷的。祝你进步!
#include "stdio.h"
void selectSort(int a[],int n){//选择排序
int change,i,j;
int mini=a[0];
int minipos=0;
for(i=0;i<n;i++){
mini=a[i];
minipos=i;
for(j=i;j<n;j++){
if(a[j]<mini){
mini=a[j];
minipos=j;
}
}
change=a[minipos];
a[minipos]=a[i];
a[i]=change;
}
}
void sub(int a[],int n) //这是一个从小到大插入排序得函数
{
int i,j,t; //t为临时变量
for(i=0;i<n;i++) //从第一个元素开始对n个元素一次进行插入排序
{ //假定当前准备对第i个元素进行插入排序,前面得i-1个元素已经
for(t=a[i],j=i-1;j>=0&&t<a[j];j--) //按从小到大排好序了。将a[i]提取出来放在临时变量t中,其从a[i-1]开始与前面得元素依次进行比较,若小于,则将该元素后移一位,直到找到第一个t>a[j],停止比较,将t放在该元素后面,即放在a[j+1]中
{
a[j+1]=a[j];
}
a[j+1]=t;
}
}
void maopao(int a[],int n)
{
int i,j,t;
for(i=1;i<n;i++) //冒泡是第i次循环在数组末尾倒数第i个位置依次产生第i大得数值
for(j=0;j<n-i;j++)
{
t=a[j+1];
if(a[j]>a[j+1]) //大值后移
{
a[j+1]=a[j];
a[j]=t;
}
}
}void print(int a[],int n){//输出数组的所有元素
int i;
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n");
}void main()
{
int i,n,c[100];
printf("请输入数组元素的个数:");
scanf("%d",&n);
printf("请依次输入各元素:\n");
for(i=0;i<n;i++)
scanf("%d",&c[i]);
sub(c,n);
printf("用插入法对这些元素从大到小进行排序:\n");
print(c,n);
maopao(c,n);
printf("用冒泡法对这些元素从大到小进行排序:\n");
print(c,n);
selectSort(c,n);
printf("用选择法对这些元素从大到小进行排序:\n");
print(c,n);
}
#include <stdio.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 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 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;
}
}// 主函数
/////////////////////////////////////////////////////////////////////
int main(int argc, char* argv[])
{
int data1[] = {10,9,8,7,6,5,4};
printf("【冒泡排序】\n");
printf(" 排序前:");
for (int i=0;i<7;i++)
printf("%d\t",data1[i]);
printf("\n");
BubbleSort(data1,7);
printf(" 排序后:");
for (i=0;i<7;i++)
printf("%d\t",data1[i]);
printf("\n\n");
int data2[] = {11,0,8,2,1,4,5};
printf("【插入排序】\n");
printf(" 排序前:");
for (i=0;i<7;i++)
printf("%d\t",data2[i]);
printf("\n");
InsertSort(data2,7);
printf(" 排序后:");
for (i=0;i<7;i++)
printf("%d\t",data2[i]);
printf("\n\n");
int data3[] = {21,20,11,8,3,4,1};
printf("【选择排序】\n");
printf(" 排序前:");
for (i=0;i<7;i++)
printf("%d\t",data3[i]);
printf("\n");
SelectSort(data3,7);
printf(" 排序后:");
for (i=0;i<7;i++)
printf("%d\t",data3[i]);
printf("\n\n");
getchar();
return 0;
}
晁承班赛: 倾情奉献: #include "stdio.h" void selectSort(int a[],int n){//选择排序int change,i,j;int mini=a[0];int minipos=0;for(i=0;i<n;i++){mini=a[i];minipos=i;for(j=i;j<n;j++){if(a[j]<mini){mini=a[j];minipos=j;}}change=a[minipos];a[minipos]=a[i];...
仙桃市18963509473: 求C语言直接插入排序,选择排序,冒泡排序的源代码,能直接运行的最好,谢谢 - ?
晁承班赛: #include<stdio.h>#define SELECTORDER int insert_order(int a[],int num) { int i,j,k; int tmp; for(i=0;i<num;i++) { tmp = a[i]; for(j=0;j<i;j++) { if(tmp<a[j]) { for(k=i;k>j;k--) { a[k]=a[k-1]; } a[j]=tmp; break; } } } return 0; } int bubble_order(int a[],int num) { int i,j; ...
仙桃市18963509473: 求调试直接插入排序算法C语言范例 - ?
晁承班赛: c++的数组第一个元素的下标是0,也就是R的第一个元素是R[0],而不是1,所以一个长度为n的数组arr的最后一个元素就是arr[n-1] 另外在main函数最后加一个return 0;是个好习惯.void main貌似是不对的,我这里的编译器通不过,应该用int ...
仙桃市18963509473: C语言直接插入法排序 请帮我分析 - ?
晁承班赛: 对数组A[0...n]中的数进行升序排序. 1.创建与数组A相同大小的数组B[0...n] 2.将A[0]放入B[0] 3.将A[1]与B[0]比较,若A[1]>B[0],则将A[1]插入到B[1],否则,B[0]移到B[1],A[1]插入B[0] 4.依次类推,将A[i]与B[i-1]进行比较,i为从1到n.若A[i]>B[i-1],则将A[i]插入到B[i]位置,否则,A[i]依次与B[i-1]、B[i-2]...B[0]进行比较,直到找出最大的t,使A[i]>B[t],则将A[i]插入到B[t+1]位置,B[t+1]...B[i-1]依次后移一个位置. 空间复杂度为O(n),时间复杂度为O(n^2)
仙桃市18963509473: C语言直接插入排序 - ?
晁承班赛: #include<stdio.h> #define max 4void insert(int a[],int count)//从小到大排序 {int i,j;for(i=2;i<=count;i++)if(a[i]<a[i-1]){a[0]=a[i];a[i]=a[i-1];for(j=i-2;a[0]<a[j];j--)a[j+1]=a[j];a[j+1]=a[0];//仔细分析排序过程} }void main() {int i;/*数组的开始下...
仙桃市18963509473: 求直接插入排序c语言完整程序 - ?
晁承班赛: #include <stdio.h>#include <stdlib.h> void insert(int *arr, int a, int n){ /*0到n-1都已排好序*/ int i; int key = a; for(i=0; i<n; i++){ if(key < arr[i]){ int j; for(j=n-1; j>=i; j--){ arr[j+1] = arr[j]; } arr[i] = key; return; } } arr[n] = key; return; } void sort(int *arr, int size){ if(...
仙桃市18963509473: 求一串用C语言编写的选择排序代码?
晁承班赛: #include <stdio.h> int main() { int a[] = {6,8,9,3,4,7,2,5,0,1}; int i, j, pick, tmp; for(i = 0; i < 10; ++i) { pick = a[i]; // 抓取一个数 for(j = i + 1; j < 10; ++j) { if(pick > a[j]) // 从后继的元素里挑选比他小的数作交换 { tmp = pick; pick = a[j]; a[j] = tmp; } } // pick...
仙桃市18963509473: 用插入法对已知数组排序 C语言急用 求各位 帮帮忙 - ?
晁承班赛: 插入排序是这样实现的:首先新建一个空列表,用于保存已排序的有序数列(我们称之为"有序列表").从原数列中取出一个数,将其插入"有序列表"中,使其仍旧保持有序状态.重复2号步骤,直至原数列为空.插入排序的平均时间...
仙桃市18963509473: C语言中在100到999中随机选择100个数,用插入排序从小到大排列 - ?
晁承班赛: 下面是完整程序.#include #include #include void InsertSort(int *a, int N) { int itemp = 0; int i,j, t; for (i = 1;i < N;i++) { itemp = i; for (j = i-1; a[itemp] < a[j] && j >= 0;j--,itemp--) { t = a[itemp]; a[itemp]=a[j];a[j]=t; } } } main(){ int a[100]; int i,N; N=100; srand(...
仙桃市18963509473: 用程序写直接插入排序算法 - ?
晁承班赛: 给你一个C语言的吧 void sort(int Array[], int len){ /*入口参数:数组名,数组长度*/ int i , k ,temp ; for(i=1; i<len; i++){ for(k=0 ; k<i && Array[k]<Array[i] ; k++);/*别忘了这里for后面的分号*/ while(k<i){ temp = Array[i]; Array[i] = Array[k]; Array[k] = temp;/*这里可以是Array[k++]=temp;那么下面的k++就不必写了*/ k++; } } }