插入排序是排序演算法的一種,它不改變原有的序列(陣列),而是建立一個新的序列,在新序列上進行操作。這裡以從小到大排序為例進行講解。
方法/步驟
基本思想及舉例說明
插入排序的基本思想是,將元素逐個新增到已經排序好的陣列中去,同時要求,插入的元素必須在正確的位置,這樣原來排序好的陣列是仍然有序的。
在實際使用中,通常是排序整個無序陣列,所以把這個無序陣列分為兩部分排序好的子陣列和待插入的元素。第一輪時,將第一個元素作為排序好的子陣列,插入第 二個元素;第二輪,將前兩個元素作為排序好的陣列,插入第三個元素。以此類推,第i輪排序時,在前i個元素的子陣列中插入第i+1個元素。直到所有元素都 加入排序好陣列。
下面,以對 3 2 4 1 進行選擇排序說明插入過程,使用j記錄元素需要插入的位置。排序目標是使陣列從小到大排列。第1輪[ 3 ] [ 2 4 1 ] (最初狀態,將第1個元素分為排序好的子陣列,其餘為待插入元素)[ 3 ] [ 2 4 1 ] (由於3>2,所以待插入位置j=1)[ 2 3 ] [ 4 1 ] (將2插入到位置j)第2輪[ 2 3 ] [ 4 1 ] (第1輪排序結果)[ 2 3 ] [ 4 1 ] (由於2<4,所以先假定j=2)[ 2 3 ] [ 4 1 ] (由於3<4,所以j=3)[ 2 3 4 ] [ 1 ] (由於4剛好在位置3,無需插入)第3輪[ 2 3 4 ] [ 1 ] (第2輪排序結果)[ 2 3 4 ] [ 1 ] (由於1<2,所以j=1)[1 2 3 4 ] (將1插入位置j,待排序元素為空,排序結束)
演算法總結及實現
選擇排序對大小為N的無序陣列R[N]進行排序,進行N-1輪選擇過程。首先將第1個元素作為已經排序好的子陣列,然後將剩餘的N-1個元素,逐個插入到已經排序好子陣列;。因此,在第 i輪排序時,前i個元素總是有序的,將第i+1個元素插入到正確的位置。
#include
#include
#define N 8
void insert_sort(int a[],int n);
//插入排序實現,這裡按從小到大排序
void insert_sort(int a[],int n)//n為陣列a的元素個數
{
//進行N-1輪插入過程
for(int i=1; i
{
//首先找到元素a[i]需要插入的位置
int j=0;
{
j++;
}
//將元素插入到正確的位置
if(i != j) //如果i==j,說明a[i]剛好在正確的位置
{
int temp = a[i];
for(int k = i; k > j; k--)
{
a[k] = a[k-1];
}
a[j] = temp;
}
}
}
int main()
{
int num[N] = {89, 38, 11, 78, 96, 44, 19, 25};
insert_sort(num, N);
for(int i=0; i
printf("%d ", num[i]);
printf("\n");
system("pause");
return 0;
}
注意:插入排序是一種穩定的排序演算法,不會改變原有序列中相同數字的順序。
插入排序是在一個已經有序的小序列的基礎上,一次插入一個元素。當然,剛開始這個有序的小序列只有1個元素,就是 第一個元素。比較是從有序序列的末尾開始,也就是想要插入的元素和已經有序的最大者開始比起,如果比它大則直接插入在其後面,否則一直往前找直到找到它該 插入的位置。如果碰見一個和插入元素相等的,那麼插入元素把想插入的元素放在相等元素的後面。所以,相等元素的前後順序沒有改變,從原無序序列出去的順序 就是排好序後的順序,所以插入排序是穩定的。