程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 9.3.1 直接插入排序

9.3.1 直接插入排序

編輯:關於C語言

    思路:每次從無序表中取出第一個元素,把它插入到有序表的合適位置,插入後,有序表繼續有序。

    初始化:取待排序中的第一個元素為為有序表,除了第一個元素的所有元素組成無序表。

    直接插入排序是由兩層嵌套循環組成。外層循環標識並決定待插入到有序數列的元素。內存循環為待插數值確定其合適位置,是插入後有序序列仍為有序序列。

    外層循環從第2個數值開始。

    內層循環中,待插入數值和它左面第1個數值比較,若左面第1個數值比它大,則左面第1個數值放到其後面的位置中即帶插入數值的位置,所以用temp保存一下待插值),然後和左面第2個比較,否則將待插入值放到它左面第1個數值的右面。依次類推。

 

#include <stdio.h>
#include <stdlib.h>
void swap(int arr[] ,int i, int j)
{
int temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
void InsertSort(int arr[], int n)
{
int i;
for(i=1;i<n;i++)  //循環從第2個數組元素開始,移位arr[0]作為最初已排序部分
{
int temp = arr[i];
int j= i-1;
while(j>=0 && arr[j]>temp)
{
arr[j+1] = arr[j];
j--;
}
arr[j+1] = temp;
}
}
void print(int arr[], int n)
{
int i;
for(i=0; i<n; i++)
{
printf("%d ",arr[i]);
}
printf("\n");
}
int main()
{
int arr[]={9, 1, 5, 8, 3, 7, 4, 6, 2};
int n = sizeof(arr)/sizeof(arr[0]);
printf("排序前:\n");
print(arr, n);
InsertSort(arr,n);
printf("排序後:\n");
print(arr, n);
system("pause");
return 0;
}

復雜度:O(n2)

穩定排序

 

本文出自 “李海川” 博客,請務必保留此出處http://lihaichuan.blog.51cto.com/498079/1282112

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved