資料結構與演算法(c++)–排序演算法
這篇文章主要簡單記錄下資料結構與演算法中的排序演算法技術
書簽
- 插入排序
- 直接插入排序
- 希爾排序
- 交換排序
- 起泡排序
- 快速排序
- 選擇排序
- 簡單選擇排序
- 堆排序
- 歸并排序
- 二路歸并排序
- 分配排序
- 桶式排序
- 各排序的時空性能
插入排序
直接插入排序
基本思想：依次將待排序序列中的每一個記錄插入到已排好序的序列中，直到全部記錄都安排好序，
直接插入排序代碼：
void Insertsort(int data[],int length){//直接插入排序
int i,j,temp;
for (i=1;i<length;i++){ //排序進行length-1次
temp=data[i]; //獲取待插元素
for(j=i-1;j>=0&&temp<data[j];j--){ //尋找插入位置
data[j+1]=data[j];
}
data[j+1]=temp;
}
}
希爾排序
基本思想：先將整個待排序記錄序列分割成若干個子序列，待整個序列基本有序時，再對全體記錄進行一次直接插入排序，
希爾排序代碼：
void Shellsort(int data[],int length){//希爾排序
int d,i,j,temp;
for (d=length/2;d>=1;d=d/2){//獲取增量d，然后再進行這屆插入排序
for (i=d;i<length;i++){
temp=data[i]; //獲取待插元素
for(j=i-d;j>=0&&temp<data[j];j=j-d)
data[j+d]=data[j];
data[j+d]=temp;
}
}
}
交換排序
起泡排序
基本思想：兩兩比較相鄰記錄，如果反序則交換，直到沒有反序的記錄為止
起泡排序代碼：
void Bubblesort(int data[],int length){//起泡排序
int j,exchange,bound,temp;
exchange=length-1;//第一趟起泡排序的區間是[0~length-1]
while(exchange!=0){
bound=exchange;
exchange=0;
for(j=0;j<bound;j++){
if(data[j]>data[j+1]){
temp=data[j];
data[j]=data[j+1];
data[j+1]=temp;
exchange=j;
}
}
}
}
快速排序
基本思想：首先選定一個軸值，將待排序記錄劃分成兩部分，左側記錄均小于或等于軸值，右側記錄均大于或等于軸值，然后分別對這兩部分重復上述程序，直到整個序列有序，
快速排序代碼：
int Partition(int data[],int first,int last){//快速排序1
int i=first,j=last,temp;
while(i<j){
while(i<j&&data[i]<=data[j])
j--;
if(i<j){
temp=data[i];
data[i]=data[j];
data[j]=temp;
i++;
}
while(i<j&&data[i]<=data[j])
i++;
if(i<j){
temp=data[i];
data[i]=data[j];
data[j]=temp;
j--;
}
}
return i;
}
void Quicksort(int data[],int first,int last){//快速排序2
if(first<last){
int pivot = Partition(data,first,last); //一次劃分
Quicksort(data,first,pivot-1); //對左側子序列進行快速排序
Quicksort(data,pivot+1,last); //對右側子序列進行快速排序
}
}
選擇排序
簡單選擇排序
基本思想：第i趟排序在待排序列中 ri ~ rn(1 ≤ i ≤ n-1)中選取最小的記錄，并和第 i 個記錄交換作為有序序列的第 i 個記錄，
簡單選擇排序代碼
void Selectsort(int data[],int length){//簡單選擇排序
int i,j,index,temp;
for(i=0;i<length-1;i++){
index=i;
for(j=i+1;j<length;j++)//在無序區獲取最小的序列
if(data[j]<data[index]) index=j;
if(index!=i){
temp=data[i];
data[i]=data[index];
data[index]=temp;
}
}
}
堆排序
基本思想：首先將待排序序列調整成一個堆，此時，選出了堆中所有記錄的最大者即堆頂元素，然后將堆頂記錄移走，并將剩余記錄再調整成堆，這樣又找出次大記錄，以此類推，直到堆中只有一個記錄，
堆排序代碼
void Sift(int data[],int k,int last){//堆排序1
int i=k;
int j=2*i+1;
int temp;
while(j<=last){
if(j<last && data[j]<data[j+1]) j++;
if(data[i]>data[j]) break;
else{
temp=data[i];
data[i]=data[j];
data[j]=temp;
i=j;
j=2*i+1;
}
}
}
void Heapsort(int data[],int length){//堆排序2
int i,temp;
for(i=ceil(length/2)-1;i>=0;i--){
Sift(data,i,length-1);
}
for(i=1;i<length;i++){
temp=data[0];
data[0]=data[length-i];
data[length-i]=temp;
Sift(data,0,length-i-1); //重建堆
}
}
歸并排序
二路歸并排序
基本思想：將待排序序列{r1, r2, …,rn}劃分為兩個長度相等的子序列{r1, r2, …,rn/2}和{rn/2+1, rn/2+2, …,rn}，分別對這兩個子序列進行排序，得到兩個有序子序列，再將這兩個有效子序列合并成一個有效子序列，
二路歸并排序代碼
void Merge(int data[],int first1,int last1,int last2,int length){//二路歸并排序1
int *temp=new int [length+1];//申請輔助空間
int i=first1;
int j=last1+1;
int k=first1;
while(i<=last1&&j<=last2){
if(data[i]<=data[j]) temp[k++]=data[i++];
else temp[k++]=data[j++];
}
while(i<=last1) temp[k++]=data[i++];
while(j<=last2) temp[k++]=data[j++];
for(i=first1;i<=last2;i++) data[i]=temp[i];//輔助空間資料傳回陣列
delete[] temp;
}
void Mergesort(int data[],int first,int last,int length){//二路歸并排序2
if(first==last) return;//子序列中只有一個記錄
else{
int mid=(first+last)/2;
Mergesort(data,first,mid,length);//歸并排序左半子序列
Mergesort(data,mid+1,last,length);//歸并排序右半子序列
Merge(data,first,mid,last,length);//合并已排序的子序列
}
}
分配排序
桶式排序
基本思想：獲取待排序序列中的最大值m，設定m+1個桶，將數值為i的記錄分配到第i個桶中，其余無數值的桶為空桶，然后再將各個桶中的記錄（忽略空桶）依次取出，
桶式排序代碼
int Findmax(int data[],int length){//桶式排序1
int i,max;
max=data[0];
for(i=1;i<length;i++){
if(data[i]>max)
max=data[i];
}
return max; //獲取最大值來創建桶陣列
}
void Bucketsort(int data[],int length){//桶式排序2
int i,m;
m=Findmax(data,length);
int *count=new int[m+1]; //創建桶陣列
for(i=0;i<=m;i++) //桶陣列全部數值賦予0
count[i]=0;
for(i=0;i<length;i++) //待排序列的數值對應的桶陣列下標，并其數值賦予1
count[data[i]]++;
for(i=0;i<=m;i++){ //取出
while(count[i]>0){
cout<<i<<" , ";
count[i]--;
}
}
}
各排序的時空性能
END！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/15128.html
標籤：其他