c語言程序設(shè)計(排序算法)-在線瀏覽
2024-09-04 09:18本頁面
【正文】 值給臨時變量,接下來的第二層循環(huán)中,如果發(fā)現(xiàn)有比這個最小位置處的元素更小的元素,則將那個更小的元素的下標賦給臨時變量,最后,在二層循環(huán)退出后,如果臨時變量改變,則說明,有比當前外層循環(huán)位置更小的元素,需要將這兩個元素交換 插入排序 有一個已經(jīng)有序的數(shù)據(jù)序列，要求在這個已經(jīng)排好的數(shù)據(jù)序列中插入一個數(shù)，但要求插入后此數(shù)據(jù)序列仍然有序，這個時候就要用到一種新的排序方法插入排序法,插入排序的基本操作就是將一個數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個新的、個數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序，時間復(fù)雜度為O(n^2)。插入算法把要排序的數(shù)組分成兩部分:第一部分包含了這個數(shù)組的所有元素，但將最后一個元素除外(讓數(shù)組多一個空間才有插入的位置)，而第二部分就只包含這一個元素(即待插入元素)。插入排序的基本思想是:每步將一個待排序的紀錄，按其關(guān)鍵碼值的大小插入前面已經(jīng)排序的文件中適當位置上，直到全部插入完為止。用ai與ai1，a i2，…，a1進行比較，找出合適的位置將ai插入；⒊重復(fù)第二步，共進行ni次插入處理，數(shù)列全部有序。即：每當兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時，就將它們互換。i10。 scanf(“%d”,amp。printf(“\n”)。j9。i9j。 進行數(shù)的調(diào)換，把大的數(shù)據(jù)調(diào)到后面。 a[i+1]=t。我們可以考慮改進為每趟循環(huán)確定兩個元素（當前趟最大和最小記錄）的位置,從而減少排序所需的循環(huán)次數(shù)。void select_sort(int a[],int n)//n為數(shù)組a的元素個數(shù){//進行N1輪選擇 for(int i=0。 i++) {int min_index = i。 jn。 } } //將第i小的數(shù)，放在第i個位置；如果剛好，就不用交換 if( i != min_index) { int temp = a[i]。 a[min_index] = temp。即：先將序列的第1個記錄看成是一個有序的子序列，然后從第2個記錄逐個進行插入，直至整個序列有序為止。 for (int i = 1。 ++i) // 從數(shù)組中的第二個元素開始 { temp = arr[i]。 while (j = 0 amp。 temp arr[j]) // 將當前元素與之前的已經(jīng)排序好的序列元素進行挨個比較 { arr[j + 1] = arr[j]。 } arr[j + 1] = temp。選擇排序算法的最差時間復(fù)雜度為O(n2)，平均時間復(fù)雜度為O(n2)。冒泡排序和插入排序時間復(fù)雜度最好的情況下是O(n)，而選擇排序時間復(fù)雜度最好的情況下是O(n2)。選擇排序的時間復(fù)雜度在以下情況下是沒有冒泡排序和插入排序的好。從空間復(fù)雜度來看，三者也沒有什么可以區(qū)分開來的。 冒泡排序和插入排序的穩(wěn)定程度都是比較穩(wěn)定的，只有選擇排序是不穩(wěn)定的。冒
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1