❶ 編寫程序用直接插入排序的演算法進行排序。
#include<stdio.h>
#include<time.h>
#include<math.h>
#include<malloc.h>
void BubbleSort(int *L,int N)
{ //冒泡
int i,j;
int t;
for(i=1;i<=N;i++)
{
for(j=N;j>i;j--)
if(L[j]<L[j-1])
{
t=L[j];
L[j]=L[j-1];
L[j-1]=t;
}
}
}
int SelectMinKey(int *L,int N,int n)
{
int i,min=n;
for(i=n+1;i<=N;i++)
if(L[i]<L[min])
min=i;
return min;
}
void SelectSort(int *L,int N)
{ //選擇
int i,j;
int t;
for(i=1;i<N;i++)
{
j=SelectMinKey(L,N,i);
if(i!=j)
{
t=L[i];
L[i]=L[j];
L[j]=t;
}
}
}
void InsertSort(int *L,int N)
{ //插入
int i,j;
for(i=2;i<=N;i++)
{
if(L[i]<L[i-1])
{
L[0]=L[i];
L[i]=L[i-1];
for(j=i-2;L[0]<L[j];j--)
L[j+1]=L[j];
L[j+1]=L[0];
}
}
}
void ShellInsert(int *L,int N, int dk)
{ // 對順序表L作一趟希爾插入排序。本演算法對演算法10.1作了以下修改：
// 1. 前後記錄位置的增量是dk，而不是1；
// 2. r[0]只是暫存單元，不是哨兵。當j<=0時，插入位置已找到。
int i,j;
for(i=dk+1;i<=N;++i)
if(L[i]<L[i-dk])
{ // 需將L.r[i]插入有序增量子表
L[0]=L[i]; // 暫存在L.r[0]
for(j=i-dk;(j>0&&L[0]<L[j]);j-=dk)
L[j+dk]=L[j]; // 記錄後移，查找插入位置
L[j+dk]=L[0]; // 插入
}
} // ShellInsert
void ShellSt(int *L,int N, int dlta[], int t)
{ // 演算法10.5
// 按增量序列dlta[0..t-1]對順序表L作希爾排序。
for(int k=0;k<t;++k)
ShellInsert(L,N, dlta[k]); // 一趟增量為dlta[k]的插入排序
} // ShellSort
void ShellSort(int *L,int N)
{ //希爾
int t=(int)log(N);
int k,*dlta;
dlta=(int*)malloc(t*4); //產生增量序列
for(k=0;k<t;k++)
dlta[k]=(int)pow(2,t-k)-1;
ShellSt(L,N,dlta,t);
}
int main()
{
int N=250;
int i,j,k;
int t;
int ti[16];
int *L;
srand(time(NULL));
printf("長度\t|冒泡\t|選擇\t|插入\t|希爾\n");
printf("--------+-------------------------------------------------------------");
for(j=0;N<100000;j++)
{
L=(int *)malloc((N+1)*4);
t=0;
for(i=1;i<=N;i++)
L[i]=rand();
ti[t++]=clock();
BubbleSort(L,N);
ti[t++]=clock();
for(i=1;i<=N;i++)
L[i]=rand();
ti[t++]=clock();
SelectSort(L,N);
ti[t++]=clock();
for(i=1;i<=N;i++)
L[i]=rand();
ti[t++]=clock();
InsertSort(L,N);
ti[t++]=clock();
for(i=1;i<=N;i++)
L[i]=rand();
ti[t++]=clock();
ShellSort(L,N);
ti[t++]=clock();
printf("\n%d\t",N);
for(k=0;k<4;k++)
printf("| %d\t",(ti[2*k+1]-ti[2*k]));
N*=5;
}
printf("\n\n");
}
//這是我們當年學數據結構時我自己寫的，給你改了一下，輸出是對隨機產生一些數，對四種演算法進行比較，有問題可以hi我啊
❷ 關於java直接插入演算法的問題
/**這是一個利用直接插入排序法寫的一個小程序；
直接插入排序是一個將待排序列中的元素p[i]與一個有序序列中的元素q[j--]比較（從後向前）,當p[i] >= q[j] （遞增排序）或 p[i] <= q[j] （遞減排序）時，q[j+1] = p[i];反之就將q[j]移位到q[j+1]為p[i]的插入預留空間且如果j==0則q[j] = p[i].
*/
public class SISort
{
public static int[] sortAscending(int []with){ //整數遞增排序
int length = with.length; //獲取待排數組的元素個數；
int []temp = new int[length];
temp[0] = with[0]; //定義一個只有一個元素的有序數組
for(int i=1; i<length; i++){
for(int j=i-1; j>=0;j--){
if(with[i] >= temp[j]){ //如果待排序列中的元素大於等於有有序序列中的元素，則插入
temp[j+1] = with[i];
break;
}
else {
temp[j+1] = temp[j]; //給待插入元素預留空間
if(j == 0)
temp[j] = with[i]; //with[[i]是有序序列中最小的，因此排在開頭
}
}
}
return temp;
}
public static double[] sortAscending(double []with){ //帶小數的遞增排序
int length = with.length; //獲取待排數組的元素個數；
double []temp = new double[length];
temp[0] = with[0]; //定義一個只有一個元素的有序數組
for(int i=1; i<length; i++){
for(int j=i-1; j>=0;j--){
if(with[i] >= temp[j]){ //如果待排序列中的元素大於等於有有序序列中的元素，則插入
temp[j+1] = with[i];
break;
}
else {
temp[j+1] = temp[j]; //給待插入元素預留空間
if(j == 0)
temp[j] = with[i]; //with[[i]是有序序列中最小的，因此排在開頭
}
}
}
return temp;
}
public static double[] sortDescending(double []with){ //遞減排序
int length = with.length; //獲取待排數組的元素個數；
double []temp = new double[length];
temp[0] = with[0]; //定義一個只有一個元素的有序數組
for(int i=1; i<length; i++){
for(int j=i-1; j>=0;j--){
if(with[i] <= temp[j]){ //如果待排序列中的元素小於等於有有序序列中的元素，則插入
temp[j+1] = with[i];
break;
}
else {
temp[j+1] = temp[j]; //給待插入元素預留空間
if(j == 0)
temp[j] = with[i]; //with[[i]是有序序列中最大的，因此排在開頭
}
}
}
return temp;
}
public static int[] sortDescending(int []with){ //遞減排序
int length = with.length; //獲取待排數組的元素個數；
int []temp = new int[length];
temp[0] = with[0]; //定義一個只有一個元素的有序數組
for(int i=1; i<length; i++){
for(int j=i-1; j>=0;j--){
if(with[i] <= temp[j]){ //如果待排序列中的元素小於等於有有序序列中的元素，則插入
temp[j+1] = with[i];
break;
}
else {
temp[j+1] = temp[j]; //給待插入元素預留空間
if(j == 0)
temp[j] = with[i]; //with[[i]是有序序列中最大的，因此排在開頭
}
}
}
return temp;
}
/* public static void main(String[] args)
{
int []test1 = {2,6,5,8,7,9,10,256,248,14}; //測試數組
double []test2 = {1.1,2.0,3,5,6,8.9,99,5};
int []temp1; //中間變數
double []temp2;
temp1 = sortDescending(test1); //測試整數遞減排序
System.out.println("get a Decreasing sequence ");
for(int i=0; i<temp1.length; i++){
System.out.println(temp1[i]);
}
temp1 = sortAscending(test1); //測試整數遞增排序
System.out.println("get a Increasing sequence");
for(int i=0; i<temp1.length; i++){
System.out.println(temp1[i]);
}
temp2 = sortDescending(test2); //測試帶小數遞減排序
System.out.println("get a Decreasing sequence ");
for(int i=0; i<temp2.length; i++){
System.out.println(temp2[i]);
}
temp2 = sortAscending(test2); //測試帶小數遞增排序
System.out.println("get a Increasing sequence");
for(int i=0; i<temp2.length; i++){
System.out.println(temp2[i]);
❸ 直接插入排序演算法實現問題
雖然沒學過java但是你的演算法錯了
while(j>=0&&a[j]>a[i]){a[j+1]=a[j];j--;}
這里的a[i]沒有存下來，應該是x=a[i];然後while(......a[j]>x);
❹ 一道數據結構，直接插入演算法的代碼。
for(i=2;i<=n;i++)//循環從第2個元素開始
{ R[0]=R[i];
for(j=i-1;R[j]>R[0];j--)
R[j+1]=R[j];
R[j+1]=R[0];
}
❺ 直接插入演算法排序問題150
選D
因為本來就有序了, 每個元素(除了第一個)和它前面的一個比較一下就行了, 一共(n-1)次
❻ 直接插入排序法。。高手進~
這個上面也說了是比較次數，那麼你前提就是比較數據。再數據中比較是只每個數據都會與其去匹配，我們這里以次數為准.
C.23、25、46、50、80、69、90、94
第一次 23將會25比較 那麼23就是 小 當前第一個位置就是23了，因為這里相對的是23和25比
第二次比較就會以25比較46 那麼第二個位置就是25了因為23與25比較過了 所以這里25是直接占據第二個位置
第三次比較就會以46比 50 第三個位置就是46 如上同理
第四次比較50和80比 如上同理 第四個位置就是50
第五次比較80和69 這里就是69是小，但是69還是會和第4個位置的50再次比較一次(這里就是第六次比較)，50小位置不動，第五個位置就是69了，這里69不會再次和前面幾個數字比較了，因為50都比起小，50已經與上面的數字已經對比過一次,所以才不需要比較
後面就是同個道理了......這樣算下來就是次數比較小了
❼ 誰能給我幾種排序的具體演算法（直接插入，折半插入，冒泡，簡單選擇，快速，堆，歸並排序）
直接插入排序
說明：逐個將後一個數加到前面的排好的序中。在直接插入排序過程中，對其中一個記錄的插入排序稱為一次
排序；直接插入排序是從第二個記錄開始進行的，因此，長度為n的記錄序列需要進行n-1次排序才能完成整個
序列的排序。時間復雜度為O(n2)。
void InsertSort(elemtype x[],int n)
/*用直接插入法對x[0]-x[n-1]排序*/
{
int i,j;
elemtype s;
for(i=0;i<n-1;i++)
{
s=x[i+1];
j=i;
while(j>-1&&s.key<x[j].key)
{
x[j+1]=x[j];
j--;
}
x[j+1]=s;
}
}
－－－－－－－－－－－－－－－－－－－－－
希爾排序
說明：希爾排序又稱縮小增量排序，增量di可以有各種不同的取法，但最後一次排序時的增量必須為1，最簡
單可取di+1=di/2（取小）。時間復雜度為O(n(log2n)2)。
void ShellSort(elemtype x[],int n,intd[],int Number)
/*用希爾排序法對記錄x[0]-x[n-1]排序，d為增量值數組*/
/*Number為增量值個數，各組內採用直接插入法排序*/
{
int i,j,k,m,Span;
elemtype s;
for(m=0;m<Number;m++)
{
Span=d[m];
for(k=0;k<Span;k++)
{
for(i=k;i<n-1;i+=Span)/*這個for之後的是「組內採用直接插入法排序」*/
{
s=x[i+Span];
j=i;
while(j>-1&&s.key<x[j].key)
{
x[j+Span]=x[j];
j-=Span;
}
x[j+Span]=s;
}
}
}
}
－－－－－－－－－－－－－－－－－－－－－－－－－－－－
直接選擇排序
說明：每次將後面的最小的找出來插入前面的已排好的序中。同理，具有n個記錄的序列要做n-1次排序。
時間復雜度為O(n2)。
void SelectSort(elemtype x[],int n)
/*用直接選擇排序法對x[0]-x[n-1]排序*/
{
int i,j,Small;
elemtype Temp;
for(i=0;i<n-1;i++)
{
Small=i;
for(j=i+1;j<n;j++)
if(x[j].key<x[Small].key)
Small=j;
if(Small!=i)
{
Temp=x[i];
x[i]=x[Small];
x[Small]=Temp;
}
}
}
－－－－－－－－－－－－－－－－－－－－－－－－－－
冒泡排序
說明：兩個兩個比較，將大的往後移。通過第一次冒泡排序，使得待排序的n個記錄中關鍵字最大的記錄排到
了序列的最後一個位置上。然後對序列中前n-1個記錄進行第二次冒泡排序。。。對於n個記錄的序列，共需進
行n次冒泡排序。時間復雜度為O(n2)。
void BubbleSort(elemtype x[],int n)
/*用冒泡排序法對x[0]-x[n-1]排序*/
{
int i,j,flag=1;
elemtype Temp;
for(i=1;i<n&&flag==1;i++)
{
flag=0;
for(j=0;j<n-i;j++)
{
if(x[j].key>x[j+1].key)
{
flag=1;
Temp=x[j];
x[j]=x[j+1];
x[j+1]=Temp;
}
}
}
}
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
快速排序
說明：又叫分區交換排序，是對冒泡排序方法的一種改進。時間復雜度為O(nlog2n)。
void QuickSort(elemtype x[],int low,int high)
/*用遞歸方法對記錄x[0]-x[n-1]進行快速排序*/
{
int i,j;
elemtype Temp;
i=low;
j=high;
Temp=x[low];
while(i<j)
{
/*在序列的右端掃描*/
while(i<j&&Temp.key<=x[j].key)j--;
if(i<j)
{
x[i]=x[j];
i++;
}
/*在序列的左端掃描*/
while(i<j&&x[i].key<Temp.key)i++;
if(i<j)
{
x[j]=x[i];
j--;
}
}
x[i]=Temp;
/*對子序列進行快速排序*/
if(low<i-1)QuickSort(x,low,i-1);
if(j+1<high)QuickSort(x,j+1,high);
}
－－－－－－－－－－－－－－－－－－－－－－－－－
歸並排序
說明：所謂歸並排序就是將兩個或兩個以上的有序數據序列合並成一個有序數據序列的過程。
時間復雜度為O(nlog2n)。
void merge(r,l,m,h,r1,r2)/*r[l,m]及r[m+1,h]分別有序，歸並後置於r2中*/
sqlist r,r2;
int l,m,h;
{
int i,j,k;
k=l;/*k是r2的指示器，i、j分別為s1、s2的指示器*/
i=l;
j=m+1;
while(i<=m&&j<=h)
{
if(r[i].key<=r[j].key)
{
r2[k]=r[i];
i++;
}
else
{
r2[k]=r[j];
j++;
}
k++;
}
if(i>m) /*s1結束*/
while(j<=h)
{
r2[k]=r[j];
j++;k++;
}
else
while(i<=m)
{
r2[k]=r[i];
i++;k++;
}
}
❽ 關於直接插入排序演算法
感覺你寫的有點復雜了，這是我用pasical寫的插入排序演算法，你看看對比一下
for j:=2 to 5 do
begin
Temp := MyArr[j];
{注意如果不用i代替j的話，dec無法通過編譯因為j的值即增有減是錯誤的}
i := j;
dec(i);
while MyArr[i] > Temp do
begin
MyArr[i+1] := MyArr[i];
Dec(i);
end;
MyArr[i+1] := Temp;
end;
❾ 直接插入排序是固定那個演算法嗎
排序演算法包括插入、交換、選擇、歸並等。
插入演算法的共性（直接、二分、希爾插入演算法）是移動數據並找到插入點，再交換數據以插入。
插入演算法的特性體現在如何找到插入點。
應該說直接插入演算法的思想是固定的，無論你具體怎麼實現。
你那不是插入排序，算是交換吧。