冒泡排序
冒泡排序的基礎上變為雙冒泡排，可減少遍歷次數序，從而實作優化
注釋代碼為錯誤代碼，不用看，但反映了不同的思考方式
//演算法8.4 冒泡排序
#include <iostream>
using namespace std;
#define MAXSIZE 20 //順序表的最大長度
typedef struct
{
int key;
char *otherinfo;
}ElemType;
//順序表的存盤結構
typedef struct
{
ElemType *r; //存盤空間的基地址
int length; //順序表長度
}SqList; //順序表型別
void BubbleSort(SqList &L)
{
//對順序表L做冒泡排序
int m,j,flag;
ElemType t;
m=L.length-1; flag=1; //flag用來標記某一趟排序是否發生交換
while((m>0)&&(flag==1))
{
flag=0; //flag置為0，如果本趟排序沒有發生交換，則不會執行下一趟排序
for(j=0;j<m;j++)
if(L.r[j].key>L.r[j+1].key)
{
flag=1; //flag置為1，表示本趟排序發生了交換
t=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=t; //交換前后兩個記錄
} //if
--m;
} //while
} //BubbleSort
// void dubBubbleSort(SqList &L){
//
// }
// void dubBubbleSort(SqList &L)
// {
// int left, right, l, r, j, i = 0;
// ElemType t;
// left =1;
// right = L.length -1;
// //必須要給l和r賦值，否則若陣列一開始就有序，則right=r中的r未賦值，即報錯
// while(left < right){
// l = left + 1;
// r = right -1;
// //第一次回圈將最大的值放到末尾
// for(j = left; j <= right; j++)
// {
// if(L.r[j].key > L.r[j + 1].key)
// {
// t=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=t;
// // r = j;
// }
// }
// right = r;
// //第二次回圈將最小的值放到了開頭
// for(j = right; j >= left; j--)
// {
// if(L.r[j].key < L.r[j - 1].key)
// {
// t=L.r[j];L.r[j]=L.r[j-1];L.r[j-1]=t;
// // l = j;
// }
// }
// left = l;
// // printf("第%d次排序結果：", i + 1);
// // i++;
// // for(j = 0; j < L.length; j++){
// // printf("%d\t", L.r[j].key);
// // }
// }
// }
void dubBubbleSort(SqList &L){
cout<<"排序程序："<<endl;
int m = L.length-1;
ElemType t;
int n=0;
while(m>n){
for (int i = 0; i < m; i++) {
if (L.r[i].key > L.r[i+1].key) {
t=L.r[i];L.r[i]=L.r[i+1];L.r[i+1]=t;
}
}
m--;
for (int i = m; i > n; i--) {
if (L.r[i].key < L.r[i-1].key) {
t=L.r[i];L.r[i]=L.r[i-1];L.r[i-1]=t;
}
}
n++;
for( int j=0;j < L.length ; j++){
cout<<L.r[j].key;
}
cout<<endl;
}
}
// int i, j, flag;
// int n=L.length-1;
// flag = 1;
// i = 1;
// while (flag != 0)
// {
// flag = 0;
// for (j = i; j < n-i; j++)
// {
// if (L.r[j].key > L.r[j + 1].key)
// {
// flag = 1;
// L.r[0].key = L.r[j].key;
// L.r[j].key = L.r[j + 1].key;
// L.r[j + 1].key = L.r[0].key;
// }
// }
// // i=1;
// for (j = n - i; j > i; j--)
// {
// if (L.r[j].key < L.r[j - 1].key)
// {
// flag = 1;
// L.r[0].key= L.r[j].key;
// L.r[j].key = L.r[j - 1].key;
// L.r[j - 1].key = L.r[0].key;
// }
// }
// i++;
// }
void Create_Sq(SqList &L)
{
int i,n;
cout<<"請輸入資料個數，不超過"<<MAXSIZE<<"個，"<<endl;
cin>>n; //輸入個數
cout<<"請輸入待排序的資料:\n";
while(n>MAXSIZE)
{
cout<<"個數超過上限，不能超過"<<MAXSIZE<<"，請重新輸入"<<endl;
cin>>n;
}
for(i=0;i<n;i++)
{
cin>>L.r[i].key;
L.length++;
}
}
void show(SqList L)
{
int i;
for(i=0;i<L.length;i++)
cout<<L.r[i].key<<" ";
cout<<endl;
}
int main()
{
SqList L;
L.r=new ElemType[MAXSIZE+1];
L.length=0;
Create_Sq(L);
BubbleSort(L);
cout<<"冒泡排序后的結果為："<<endl;
show(L);
SqList L2;
L2.length=0;
L2.r=new ElemType[MAXSIZE+1];
Create_Sq(L2);
dubBubbleSort(L2);
cout<<"雙冒泡排序后的結果為："<<endl;
show(L2);
}
ok，以上就是雙冒泡排序
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/115745.html
標籤：其他
下一篇：排序-插入排序