網站首頁常識百科 >正文
1、在實際使用中,通常是排序整個無序數(shù)組,所以把這個無序數(shù)組分為兩部分排序好的子數(shù)組和待插入的元素。第一輪時,將第一個元素作為排序好的子數(shù)組,插入第二個元素;第二輪,將前兩個元素作為排序好的數(shù)組,插入第三個元素。以此類推,第i輪排序時,在前i個元素的子數(shù)組中插入第i+1個元素。直到所有元素都加入排序好數(shù)組。
2、下面,以對 3? 2? 4? 1 進行選擇排序說明插入過程,使用j記錄元素需要插入的位置。排序目標是使數(shù)組從小到大排列。第1輪[ 3 ]? [ 2? 4? 1 ]? (最初狀態(tài),將第1個元素分為排序好的子數(shù)組,其余為待插入元素)[ 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,待排序元素為空,排序結束)
3、算法總結及實現(xiàn)選擇排序對大小為N的無序數(shù)組R[N]進行排序,進行N-1輪選擇過程。首先將第1個元素作為已經排序好的子數(shù)組,然后將剩余的N-1個元素,逐個插入到已經排序好子數(shù)組;。因此,在第 i輪排序時,前i個元素總是有序的,將第i+1個元素插入到正確的位置。
4、#include<stdio.h>#include<stdlib.h>#define N 8void insert_sort(int a[],int n);//插入排序實現(xiàn),這里按從小到大排序void insert_sort(int a[],int n)//n為數(shù)組a的元素個數(shù){//進行N-1輪插入過程for(int i=1; i<n; i++){//首先找到元素a[i]需要插入的位置int j=0;while( (a[j]<a[i]) && (j<i)){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<N; i++)printf("%d ?", num[i]);printf("\n");system("pause");return 0;}
5、注意:插入排序是一種穩(wěn)定的排序算法,不會改變原有序列中相同數(shù)字的順序。
6、插入排序是在一個已經有序的小序列的基礎上,一次插入一個元素。當然,剛開始這個有序的小序列只有1個元素,就是第一個元素。比較是從有序序列的末尾開始,也就是想要插入的元素和已經有序的最大者開始比起,如果比它大則直接插入在其后面,否則一直往前找直到找到它該插入的位置。如果碰見一個和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后順序沒有改變,從原無序序列出去的順序就是排好序后的順序,所以插入排序是穩(wěn)定的。
本文到此結束,希望對大家有所幫助。
版權說明:本文由用戶上傳,如有侵權請聯(lián)系刪除!
猜你喜歡:
- 2022-06-07唐博英(唐博英)
- 2022-06-07多少愛可以重來演員表(多少愛可以重來)
- 2022-06-07重生之超級公子 起點中文網作者公子小川作品(重生之超級公子 起點中文網作者公子小川作品)
- 2022-06-07大連老賴名單(大連老百姓網)
- 2022-06-07win10計算機右鍵管理打不開(win10計算機右鍵管理打不開)
- 2022-06-07吳宜燦離職后續(xù)(吳宜燦)
- 2022-06-07什么牌子的兒童防曬霜好用(兒童防曬霜哪個牌子好用兒童防曬霜熱賣排行榜)
最新文章:
- 2022-06-07傳承的反義詞是什么(傳承條目)
- 2022-06-07桃子好保存嗎(桃子能用保鮮劑嗎詳細介紹)
- 2022-06-07九財商中小企業(yè)賺錢的九把鑰匙
- 2022-06-07唐博英(唐博英)
- 2022-06-07我國社會主義法制建設的基本要求(我國社會主義法制建設的基本要求是什么)
- 2022-06-07多少愛可以重來演員表(多少愛可以重來)
- 2022-06-07重生之超級公子 起點中文網作者公子小川作品(重生之超級公子 起點中文網作者公子小川作品)
- 2022-06-07win10怎么清理C盤空間(win10清理C盤空間 快速有效 不信你試試)
- 2022-06-07運程是什么意思(運程)
- 2022-06-07干羊肚菌存放多久(干羊肚菌可以放多久放哪里詳細介紹)
- 2022-06-07汽車內飾都有哪些(汽車的內部裝飾有哪些)
- 2022-06-07高中立體幾何中的三棱錐概念什么是正三棱錐是四邊都是正三角形的椎體嗎但是正金字塔的定義并不是地面上的正多邊形頂點在地面上的投影不是正好在底部的中心嗎如果一個正三角形金字塔的底部
- 2022-06-07帝豪gl下雨天車門打不開怎么回事(吉利帝豪gl下雨車門鎖打不開是什么原因)
- 2022-06-0718烏克蘭客機墜毀事故犯罪(18烏克蘭客機墜毀事故)
- 2022-06-07年輕母親和兒子同臺(年輕母親4)
- 熱點推薦
- 熱評文章