C++排序方法補充
---恢復內容開始---
1.插入排序:
思想:當讀入一個元素的時候,在已經排序好的序列中,搜尋它的正確位置,再放入讀入的元素。
但是,有一個不可以忽略的問題是:在插入元素之前,應當先將它後面的語速後移一位,以保證插入位置的原有元素不被覆蓋。
例子:
有8個數。
36 25 48 12 65 43 20 58
排序方案;
第0步:[36] 25 48 12 65 43 20 58
第一步:[25 36] 48 12 65 43 20 58
第二步:[25 36 48] 12 65 43 20 58
第三步:[12 25 36 48] 65 43 20 58
第四步:[12 25 36 48 65] 43 20 58
第五步:[12 25 36 43 48 65] 20 58
第六步:[12 20 25 36 43 48 65] 58
第七步:[12 20 25 36 43 48 58 65]
程式:
#include<bits/stdc++.h> using namespace std; int main() { int n,i,j,t,a[1000000]; cin>>n; for(int i=0;i<n;i++) { cin>>a[i]; } for(int i=0;i<=n;i++) { for(int j=i-1;j>=0;j--) { if(a[j]<a[i])break; } if(j!=i-1) { t=a[i]; for(int k=i-1;k>j;k--) { a[k+1]=a[k]; a[k+1]=t; } } } for(int i=0;i<n;i++) { cout<<a[i]<<" "; } }
2.桶排序:
細想:若待排序的值在一個明顯有限範圍內時,可設計有限個有序桶,待排序的值裝入對應的桶(值可以為多個),桶號就是待排序的值,順序輸出各桶的值,將得到有序的數列。
例子:
輸入n個0到100以內的整數,由小到大排序輸出。
輸入示例;
10
2 3 1 2 4 55 3 55 3 2
輸出示例:
1 2 2 2 3 3 3 4 55 55
程式;
#include<iostream> #include<cstdio> using namespace std; int main() { int b[10000]={0},n,k; //memset(b,0,sizeof(b));//將陣列全部變為零 cin>>n; for(int i=1;i<=n;i++) { cin>>k;b[k]++; } for(int i=0;i<=100;i++) { while(b[i]>0) { cout<<i<<" "; b[i]--; } } }