表插入排序c語言
1. c語言鏈表插入排序問題
//修改如下
#include
<stdio.h>
#include
<stdlib.h>
typedef
struct
node
{
int
xh;
char
sname[8];
int
sx;
int
yw;
int
zf;
int
mc;
struct
node
*next;
}linklist;
void
main()
{
linklist
*head;
linklist
*s=NULL;
//創建
鏈表時所用的指針。。
linklist
*p=NULL;//
輸出
鏈表時所用的指針。。
linklist
*q=NULL;
linklist
*g=NULL;
char
ch;
head
=
NULL;//開始時
鏈表的頭為空；
printf("
輸入
y
進入循環\n");
scanf("%c",&ch);
while(ch
=='y'||ch=='Y')
{
s=(linklist*)malloc(sizeof(linklist));//給鏈表建立個空間
printf("輸入學號");
scanf("%d",&s->xh);
printf("輸入姓名");
scanf("%s",s->sname);
printf("輸入數學成績");
scanf("%d",&s->sx);
printf("輸入語文成績");
scanf("%d",&s->yw);
s->zf=s->sx+s->yw;
s->next
=
NULL;
if(head
==
NULL||head->zf<s->zf)
{
s->next=head;
head=s;
}
else
{
p=head;
q=p->next;
while(q!=NULL&&s->zf
<=
q->zf)
{
p=q;
q=q->next;
}
s->next=q;
p->next=s;
}
getchar();//修改
printf("
繼續輸入按y\n");//修改
scanf("%c",&ch);
}
//輸出鏈表
g=head;
while(g!=NULL)
{
printf("%4d",g->xh);
printf("%4s",g->sname);
printf("%4d",g->sx);
printf("%4d",g->yw);
printf("%4d",g->zf);
printf("\n
");
g=g->next;//修改
}
}
2. 插入排序 C語言
#include<stdio.h>
intmain()
{intt,n,i,j,x,a[200];
scanf("%d",&t);
for(i=0;i<t;i++)
{scanf("%d%d",&n,&x);
for(j=1;j<=n;j++)
scanf("%d",&a[j]);
a[0]=x;
j=n;
while(a[j]>x)
{a[j+1]=a[j];
j--;
}
a[j+1]=x;
for(i=1;i<=n;i++)
printf("%d",a[i]);
printf("%d
",a[i]);
}
return0;
}
3. C語言插入排序法
用c實現的插入排序法，先輸入10個數，然後利用插入排序法進行排序，將結果輸出。
#include "stdio.h"
#include "conio.h"
main()
{
int a[10],r[11];
int *p;
int i,j;
for(i=0;i<10;i++)
{
p=&a[i];
printf("please scan the NO:
%d\n",i);
scanf("%d",p);
r[i+1]=a[i];
}
r[0]=1;
for(i=2;i<=10;i++)
{
r[0]=r[i];
j=i-1;
while(r[j]>r[0])
{
r[j+1]=r[j];
j--;
}
r[j+1]=r[0];
}
for(i=1;i<=10;i++) {p=&r[i];printf("form min to max the NO: %d value=%d\n",i,*p);}
getch();
}
4. C語言插入排序由小到大的代碼
C語言插入排序由小到大的代碼如下：
int main()
{
int a[10];
int i,j,temp=0;
int k,x=0;
printf("輸入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[j]<a[i])
k = j;
temp=a[i];
a[i]=a[k];
a[k]=temp;
}
printf("排序後： ");
for(i=0;i<10;i++)
printf("%d ",a[i]);
getchar();getchar();
}
(4)表插入排序c語言擴展閱讀：
數學函數
所在函數庫為math.h、stdio.h、string.h、float.h
int abs(int i) 返回整型參數i的絕對值
double cabs(struct complex znum) 返回復數znum的絕對值
double fabs(double x) 返回雙精度參數x的絕對值
long labs(long n) 返回長整型參數n的絕對值
double exp(double x) 返回指數函數ex的值
doublefrexp(double value,int *eptr) 返回value=x*2n中x的值,n存貯在eptr中
doubleldexp(double value,int exp); 返回value*2exp的值
double log(double x) 返回logex的值
double log10(double x) 返回log10x的值
double pow(double x,double y) 返回x^y的值
doublepow10(int p) 返回10^p的值
double sqrt(double x) 返回+√x的值
5. C語言插入排序演算法
int main ()
{
int i;
DataType a[MaxSize];
SqList L;
srand((unsigned)time(NULL));
for (i=0;i<MaxSize;i++)
{
int number = rand()%MaxSize + 1;
//printf ("%d ",number);
a[i].key = number;
L.data[i].key = a[i].key;
}
return 0;
}
6. c語言插入法排序的演算法步驟
演算法描述
一般來說，插入排序都採用in-place在數組上實現。具體演算法描述如下：
從第一個元素開始，該元素可以認為已經被排序
取出下一個元素，在已經排序的元素序列中從後向前掃描
如果該元素（已排序）大於新元素，將該元素移到下一位置
重復步驟3，直到找到已排序的元素小於或者等於新元素的位置
將新元素插入到該位置後
重復步驟2~5
如果比較操作的代價比交換操作大的話，可以採用二分查找法來減少比較操作的數目。該演算法可以認為是插入排序的一個變種，稱為二分查找排序。
范常式式碼
void insertion_sort(int array[], int first, int last)
{
int i,j;
int temp;
for (i = first+1; i<=last;i++)
{
temp = array[i];
j=i-1;
while((j>=first) && (array[j] > temp))
{
array[j+1] = array[j];
j--;
}
array[j+1] = temp;
}
}
7. 求表插入排序的C語言代碼，數據結構的，能在VC里運行的。
三種插入排序都給你寫好啦！
#include<string.h>
#include<ctype.h>
#include<malloc.h> /* malloc()等 */
#include<limits.h> /* INT_MAX等 */
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<stdlib.h> /* atoi() */
#include<io.h> /* eof() */
#include<math.h> /* floor(),ceil(),abs() */
#include<process.h> /* exit() */
/* 函數結果狀態代碼 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
/* #define OVERFLOW -2 因為在math.h中已定義OVERFLOW的值為3,故去掉此行 */
typedef int Status; /* Status是函數的類型,其值是函數結果狀態代碼，如OK等 */
typedef int Boolean; /* Boolean是布爾類型,其值是TRUE或FALSE */
#define MAXSIZE 20 /* 一個用作示例的小順序表的最大長度 */
/*對兩個數值型關鍵字的比較約定為如下的宏定義 */
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
typedef int KeyType; /* 定義關鍵字類型為整型 */
typedef int InfoType; /* 定義其它數據項的類型 */
typedef struct
{
KeyType key; /* 關鍵字項 */
InfoType otherinfo; /* 其它數據項，具體類型在主程中定義 */
}RedType; /* 記錄類型 */
typedef struct
{
RedType r[MAXSIZE+1]; /* r[0]閑置或用作哨兵單元 */
int length; /* 順序表長度 */
}SqList; /* 順序表類型 */
void InsertSort(SqList *L)
{ /* 對順序表L作直接插入排序。*/
int i,j;
for(i=2;i<=(*L).length;++i)
if LT((*L).r[i].key,(*L).r[i-1].key) /* "<",需將L.r[i]插入有序子表 */
{
(*L).r[0]=(*L).r[i]; /* 復制為哨兵 */
for(j=i-1;LT((*L).r[0].key,(*L).r[j].key);--j)
(*L).r[j+1]=(*L).r[j]; /* 記錄後移 */
(*L).r[j+1]=(*L).r[0]; /* 插入到正確位置 */
}
}
void BInsertSort(SqList *L)
{ /* 對順序表L作折半插入排序。*/
int i,j,m,low,high;
for(i=2;i<=(*L).length;++i)
{
(*L).r[0]=(*L).r[i]; /* 將L.r[i]暫存到L.r[0] */
low=1;
high=i-1;
while(low<=high)
{ /* 在r[low..high]中折半查找有序插入的位置 */
m=(low+high)/2; /* 折半 */
if LT((*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]; /* 插入 */
}
}
void P2_InsertSort(SqList *L)
{ /* 2_路插入排序 */
int i,j,first,final;
RedType *d;
d=(RedType*)malloc((*L).length*sizeof(RedType)); /* 生成L.length個記錄的臨時空間 */
d[0]=(*L).r[1]; /* 設L的第1個記錄為d中排好序的記錄(在位置[0]) */
first=final=0; /* first、final分別指示d中排好序的記錄的第1個和最後1個記錄的位置 */
for(i=2;i<=(*L).length;++i)
{ /* 依次將L的第2個～最後1個記錄插入d中 */
if((*L).r[i].key<d[first].key)
{ /* 待插記錄小於d中最小值，插到d[first]之前(不需移動d數組的元素) */
first=(first-1+(*L).length)%(*L).length; /* 設d為循環向量 */
d[first]=(*L).r[i];
}
else if((*L).r[i].key>d[final].key)
{ /* 待插記錄大於d中最大值，插到d[final]之後(不需移動d數組的元素) */
final=final+1;
d[final]=(*L).r[i];
}
else
{ /* 待插記錄大於d中最小值，小於d中最大值，插到d的中間(需要移動d數組的元素) */
j=final++; /* 移動d的尾部元素以便按序插入記錄 */
while((*L).r[i].key<d[j].key)
{
d[(j+1)%(*L).length]=d[j];
j=(j-1+(*L).length)%(*L).length;
}
d[j+1]=(*L).r[i];
}
}
for(i=1;i<=(*L).length;i++) /* 把d賦給L.r */
(*L).r[i]=d[(i+first-1)%(*L).length]; /* 線性關系 */
}
void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}
#define N 8
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
SqList l1,l2,l3;
int i;
for(i=0;i<N;i++) /* 給l1.r賦值 */
l1.r[i+1]=d[i];
l1.length=N;
l2=l3=l1; /* 復制順序表l2、l3與l1相同 */
printf("排序前:\n");
print(l1);
InsertSort(&l1);
printf("直接插入排序後:\n");
print(l1);
BInsertSort(&l2);
printf("折半插入排序後:\n");
print(l2);
P2_InsertSort(&l3);
printf("2_路插入排序後:\n");
print(l3);
}
8. C語言的插入排序法是什麼
插入排序(insertion sort)
如果需要對一個小型數組進行升序排列，那麼可以選用插入排序，插入排序可以用打牌時對摸起的牌根據牌的點數來對其進行插入排列來描述。
可以把左手中的牌比做已經摸起的牌，即已經被排列好的牌，左手可以容納的牌數的空間可以假想為和要摸的牌的總數相同；而在桌子上的那部分沒摸的牌則是未被排序的牌，這二者的關系可以抽象為數組中已經被排序好的部分和未被排序好的部分。
一開始摸起的第一張牌不需要排序，可以認定其為已排序的牌。
如果用外層循環for來表示摸起的牌的話，則可以抽象為：
// 對象數組
// 桌子上的牌
int A[] = {5,1,3,6,2,4};
// 從數組的第二個元素開始抽取
for(int i = 1; i < sizeof A/sizeof A[0]; ++i)
{
int pick = A[i]; // 被摸起的牌
int j = i - 1; // j記錄已排序部分的最後一張牌的位置
. . .
}
而後摸起的排要根據排列策略和先前摸起的牌的點數的大小來確定其插入的合適位置，這里示範的排列策略是升序排列，摸起了這張牌後，便自右向左地和手中的牌進行比較。
把pick稱作摸起的牌，如果pick比手中的牌小，則手中較大的那張牌就向右挪一位，pick再和下一張牌做比較，如果下一張牌仍然比pick大，那麼那張牌便也向右移動一個位置，依此類推。
如果手中下一張和pick比較的牌比pick小，那麼pick就被插入在了手中前一張牌移動後空下的位置；
或者手中所有的牌都比pick大，那麼所有的牌就都向右移動過一個位置，所以pick最終被插入在了手中最左邊的位置。
這個過程可以抽象為：
// 對象數組
// 桌子上的牌
int A[] = {5,1,3,6,2,4};
// 從數組的第二個元素開始抽取
for(int i = 1; i < sizeof A/sizeof A[0]; ++i)
{
int pick = A[i]; // 被摸起的牌
int j = i - 1; // j記錄已排序部分的最後一張牌的位置
// 如果循環了j+1次，即j = -1時還未找到比pick小的牌
// 那麼pick就是最小的牌被插入在位置A[0]處
// A[j]是當前手中和pick進行比較的牌
while(j >= 0 && A[j] > pick)
{
// 未找到可插入位置，則A[j]向後挪一位
A[j+1] = A[j];
// j減1繼續向左定位手中下一張供和pick比較的牌--j;
}
// while結束後，j+1所表達的位置便是pick可以插入的位置
A[j+1] = pick;
}
// 對於有N個元素的數組A，採用插入排序法排序時，當外層循環進行了N-1次後排序完畢
9. 對單鏈表中元素按插入方法排序的C語言描述演算法如下，其中L為鏈表頭結點指針。請填充演算法中標出的空白處。
這個演算法有兩個循環，我們姑且稱其為外循環和內循環，誠如其他樓的一位網友所言，其內循環在第一次判斷時進不去是正常的，但後面會進去。為什麼呢？首先我們來理一下這個演算法的大體思路：這是一個針對單鏈表的排序演算法，就是說給定一個單鏈表，我們要把按照結點（這里不對頭結點進行排序，即這里討論的結點不包括頭結點）的數據域中的data值的大小從小到大進行排序，得到新的排序後的有序鏈表。我們先把鏈表的頭結點之後的部分鏈表拆下來，即p=L->next，L->next=NULL，這樣我們就拆分原來的鏈表變成了現在的兩個鏈表（我們稱只有一個頭結點的鏈表為L1，另一個全為數據項結點的鏈表為L2）。接下來我們一個一個從L2剝下單獨的結點，放到L1中，其中如果L1中已經有數據項結點，則要先進行data項比較再找到合適的地方插入。直到最後L2中的結點全部拆下來並裝到了L1上，於是排序完畢，此時的L1擁有與原來的單鏈表相同的頭結點，但是排列有序的數據項結點。
理完了整個演算法的思路後再回去看代碼就很明顯，外循環判斷「p!=NULL」的意義在於判斷L2鏈表中是否還有沒有剝完的結點，而內循環中要先判斷「q!=NULL」的第一層意義在於判斷L1鏈表是不是一個只有頭結點的空表（即無數據項結點），如果是，則直接插入，如果不是，則判斷目前L1頭結點的下一個結點q的data值是否小於等於剛從L2剝下來的結點p的data值，如果是，則說明這個p結點應該安放的位置還在q結點之後，我們還要繼續往下找，直到找到q->data > p->data的結點q或者已經到了鏈表的末尾（這也是q!=NULL的第二層意義），則停止尋找，並將p結點就放在這個位置。
說了半天忘了回答樓主的疑問，為什麼內循環永遠不會進去嗎？不是，只是第一次不會進去（當然，如果原單鏈表本身就是一個只有頭結點的鏈表時那麼後面也不會再進去了，因為空表根本不需要排序），而後面就會進去，具體原因見我上述分析即可知。
10. C語言插入排序怎麼編
一般來說，插入排序都採用in-place在數組上實現。具體演算法描述如下： 1. 從第一個元素開始，該元素可以認為已經被排序 2. 取出下一個元素，在已經排序的元素序列中從後向前掃描 3. 如果該元素（已排序）大於新元素，將該元素移到下一位置 4. 重復步驟3，直到找到已排序的元素小於或者等於新元素的位置 5. 將新元素插入到下一位置中 6. 重復步驟2 如果比較操作的代價比交換操作大的話，可以採用二分查找法來減少比較操作的數目。該演算法可以認為是插入排序的一個變種，稱為二分查找排序。
輸入參數中，需要排序的數組為array[],起始索引為first，終止索引為last。示例代碼的函數採用in-place排序，調用完成後，array[]中從first到last處於升序排列。
void insertion_sort(int array[], unsigned int first, unsigned int last)
{ int i,j;
int temp;
for (i = first+1; i<=last;i++)
{ temp = array[i]; j=i-1; //與已排序的數逐一比較, 大於temp時, 該數移後
while((j>=first) && (array[j] > temp))
{ array[j+1] = array[j];
j--;
}
array[j+1] = temp;
}
}
這個更好:
void InsertSort(char array[],unsigned int n)
{ int i,j;
int temp;
for(i=1;i<n;i++)
{
temp = array[i];//store the original sorted array in temp
for(j=i ; j>0 && temp < array[j-1] ; j--)//compare the new array with temp
{
array[j]=array[j-1];//all larger elements are moved one pot to the right
}
array[j]=temp;
}
}