① 請教關於撲克的演算法
我代碼已經寫的有些眉目了，隨機發牌已經寫完，擺放演算法在紙上畫出來了應該沒什麼大問題，代碼明天寫，明天下班繼續回來看看，應該能搞定。
到時候思考過程我都會寫出來，代碼部分會放到我的空間，敬請留意。
回答者：風騷的可樂 - 千總 四級 12-13 01:40
----------------------------
問題描述：
列印3行，每行9張撲克，用戶隨機記錄一張之後輸入該撲克所在的行號（1-3）
程序打亂順序兩次，用戶再輸入所記錄的撲克在新的矩陣中的行號，也是兩次。
程序給出准確結果。
--------------------------------------------------------------
分析：
假設：54張撲克對應54個整數，隨機抽取27個排成矩陣。
假設：第i次打亂之後的矩陣為M(i)，用戶第i次輸入的行號為L(i)。這里i取1,2或3。
進行第一次打亂，我們將得到用戶輸入的兩個數，L(1)和L(2)。此時，我們需要保證同時在M(1)中第L(1)行，且在M(2)中第L(2)行的元素足夠
少，假如這時候滿足條件的數組是A(1)，其中含元素N(1)個。
那麼我們再進行第2次打亂，用戶輸入L(3)。那麼這時候，我們要保證，同時在M(3)中第L(3)行，且在數組A(1)中的元素，有且僅有1個，也就
是N(2)必須為1。
--------------------------------------------------------------
來看一個例子：
假設有如下的整數矩陣
[1] [2] [3]
[4] [5] [6]
[7] [8] [9]
假定我記錄了8，那麼L(1)=3，那麼程序應該知道，用戶記錄的數字要麼是7，要麼8，要麼9。這時候需要把這3個數放到不同的3行里，這樣下
次用戶輸入行數就能確定兩次的交集了。
看看這種移位：
[1] [5] [9]
[4] [8] [3]
[7] [2] [6]
如果擁護輸入L(2)=2，程序將可以直接判定，第一次在{ 7,8,9 }中，且第2次在{ 4,8,3 }中的，必然是8這個數。
同理，我們也可以這樣移位：
[1] [8] [6]
[4] [2] [9]
[7] [5] [3]
這樣，用戶的輸入就應該是L(2)=1，判定方式同上類似。
可以得出結論，對於3*3的矩陣，可以通過2次判定得出結果。
下面我們把結論推廣到27個數：
假定有如下的9*3矩陣
[T1] [T2] [T3]
[T4] [T5] [T6]
[T7] [T8] [T9]
其中，Ti(i=1~9)分別是3*1的矩陣，我們可以通過L(1)和L(2)確定i，因為Ti只有1行3個數，所以後面可以直接通過以上的「按列移位」方法來
確定具體是哪個數。
--------------------------------------------------------------
下面給出測試代碼，其中有部分變數和注釋是沒有實際意義的，如果你仔細看過，相信很容易將他們挑出來刪除掉。
代碼說明：
(1) 為了方便，我沒有將關鍵代碼寫成函數形式，如果寫成函數形式的話會比較便於推廣到n，而不僅僅局限於27個數。
(2) 為了方便，我沒有寫整數數組與撲克牌的轉換代碼，實際上這部分功能可以簡單的通過數組對應來實現，請自行完成。
(3) 為了方便，代碼中用到很多swap，實際上，應該使用自己編寫的交換函數來實現這個功能，為了擴展方便，swap的參數已經被寫成有規律
的形式
(4) 調試環境：VC6_SP6+WinXP，轉載請註明出處：http://hi..com/crazycola，代碼開放，抄襲可恥
#include <time.h>
#include <iostream>
#include <cstdlib>
#include <iomanip>
using namespace std;
void printArr(const int* pArr)
{
for( int i=0; i<3; i++ )
{
for( int j=0; j<9; j++ )
cout << setw(3) << pArr[i*9+j] << " ";
cout << endl; // 抄襲可恥
}
}
void main()
{
int line = 0;
srand( (unsigned)time( NULL ) );
int *iArr = new int[27];
int tag = 0;
for( int i1=0; i1<27; i1++ )
{
char cola_temp1 = 'x'; // when you just this without going through
iArr[i1]=1+rand()%54; // you'll be dammed
if( i1==0 ) continue;
do {
tag = 0;
for( int j=0; j<i1; j++ )
if( iArr[j] == iArr[i1] )
{
iArr[i1]=1+rand()%54;
tag = 1;
}
} while( tag==1 );
// cout << iArr[i1] << endl;
}
printArr(iArr);
char cola_temp2 = 't';
cin >> line; // first
int *iArr2 = new int[9];
for( int i3=0; i3<9; i3++ )
iArr2[i3] = iArr[(line-1)*9+i3]; // aha, it's sunny outside
swap(iArr[ 0*9+ 3],iArr[ 1*9+ 3]); swap(iArr[ 0*9+ 4],iArr[ 1*9+ 4]); swap(iArr[ 0*9+ 5],iArr[ 1*9+ 5]);
swap(iArr[ 0*9+ 3],iArr[ 2*9+ 3]); swap(iArr[ 0*9+ 4],iArr[ 2*9+ 4]); swap(iArr[ 0*9+ 5],iArr[ 2*9+ 5]);
swap(iArr[ 0*9+ 6],iArr[ 2*9+ 6]); swap(iArr[ 0*9+ 7],iArr[ 2*9+ 7]); swap(iArr[ 0*9+ 8],iArr[ 2*9+ 8]);
swap(iArr[ 0*9+ 6],iArr[ 1*9+ 6]); swap(iArr[ 0*9+ 7],iArr[ 1*9+ 7]); swap(iArr[ 0*9+ 8],iArr[ 1*9+ 8]);
printArr(iArr);
cin >> line; //second
int smallMatrixFoot = -1;
int *iArr3 = new int[3];
char cola_temp3 = '5'; // 抄襲可恥
for( int i4=0,k=0; i4<9; i4++ )
for( int j=0; j<9; j++ )
if( iArr2[j]==iArr[(line-1)*9+i4] )
{
if( k==0 ) smallMatrixFoot = (line-1)*9+i4; // save for future use
// smallMatrixFoot % 9 = col_num, and ( smallMatrixFoot - col_num
) / 9 = row_num
iArr3[k++] = iArr2[j];
}
// -- start: for test only
/*for( int dbg01=0; dbg01<3; dbg01++ )
cout << iArr3[dbg01] << " ";
cout<<endl;*/
// --end: for test only
int col_num = smallMatrixFoot % 9;
swap(iArr[ 0*9+col_num+1],iArr[ 1*9+col_num+1]); swap(iArr[ 0*9+col_num+1],iArr[ 2*9+col_num+1]);
swap(iArr[ 0*9+col_num+2],iArr[ 2*9+col_num+2]); swap(iArr[ 0*9+col_num+2],iArr[ 1*9+col_num+2]);
printArr(iArr);
char cola_temp = '0';
cin >> line; //third
int bingo = -1;
for( int i5=0; i5<3; i5++ )
if( iArr3[i5]==iArr[(line-1)*9+col_num+i5] )
bingo = iArr3[i5]; // i'm not so happy
// -- start: for test only
/*else
cout << iArr3[i5] << "!=" << iArr[line*9+col_num+i5] << endl;*/
// --end: for test only
cout << endl << "wow, you've remembered " << bingo << " !" << endl;
delete [] iArr3; iArr3 = NULL;
delete [] iArr2; iArr2 = NULL;
delete [] iArr; iArr = NULL; // 抄襲可恥
}
② C語言宏定義#define SWAP(a,b)用異或演算法互換a，b兩個整數，並用C語言演示出來。
#include <stdio.h>
#define SWAP(a,b) a^=b, b^=a, a^=b
main()
{
int x = 3, y = 4;
printf("x = %d, y = %d\n", x, y);
SWAP(a, b);
printf("互換後 x = %d, y=%d\n", x, y);
}
③ 用C++交換排序
所謂交換，就是根據序列中兩個記錄值的比較結果來對換這兩個記錄在序列中的位置。交換排序的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動。常見的交換排序有冒泡排序（Bubble Sort），雞尾酒排序（Cocktail Sort），奇偶排序（OddEven Sort），地精排序（Gnome Sort），快速排序（Quick Sort），臭皮匠排序（Stooge Sort），梳排序（Comb Sort），Bogo排序（Bogo sort）。下面介紹前六種：
（一）冒泡排序
最差時間復雜度：O(n^2)
最優時間復雜度：O(n)
平均時間復雜度：O(n^2)
最差空間復雜度：總共O(n)，需要輔助空間O(1)
穩定性：穩定
冒泡排序（Bubble Sort），它重復地走訪過要排序的數列，一次比較兩個元素如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。
冒泡排序演算法的運作如下：
1.比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2.對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。
3.針對所有的元素重復以上的步驟，除了最後一個。
4.持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。
實現代碼：
[cpp] view plain
void BubbleSort(int *a, int len)
{
for (int i=0; i<len; i++)
{
for (int j=len-1; j>i; j--)
{
if (a[j]<a[j-1])
swap(a[j], a[j-1]);
}
}
}
（二）雞尾酒排序
最差時間復雜度：O(n^2)
最優時間復雜度：O(n)
平均時間復雜度：O(n^2)
穩定性：穩定
雞尾酒排序（Cocktail sort），是冒泡排序的一種變形。它與冒泡排序的不同之處在於排序時是以雙向在序列中進行排序。數組中的數字本是無規律的排放，先對數組從左到右進行冒泡排序（升序），把最大值放到最右端，然後對數組從右到左進行冒泡排序（降序），把最小的數字放到最左端。然後再以此類推，以此改變冒泡的方向，並不斷縮小未排序元素的范圍。直到在一趟雙向冒泡後沒有發生交換，排序結束。
實現代碼：
[cpp] view plain
void CocktailSort(int* a, int len)
{
int bottom = 0;
int top = len-1;
bool swapped = true;
while (swapped)
{
swapped = false;
for (int i=bottom; i<top; i++)
{
if (a[i]>a[i+1])
{
swap(a[i], a[i+1]);
swapped = true;
}
}
top = top-1;
for (int i=top; i>bottom; i--)
{
if (a[i]<a[i-1])
{
swap(a[i], a[i-1]);
swapped = true;
}
}
bottom = bottom+1;
}
}
（三）奇偶排序
最差時間復雜度：O(n^2)
穩定性：穩定
奇偶排序（OddEven Sort），是一種相對簡單的排序演算法，最初發明用於有本地互聯的並行計算。此演算法通過比較數組中相鄰的（奇-偶）位置數字對，如果該奇偶對是錯誤的順序（第一個大於第二個），則交換。下一步重復該操作，但針對所有的（偶-奇）位置數字對。如此交替下去，直到不發生交換，則排序結束。
在並行計算排序中，使用該演算法，每個處理器對應處理一個值，並僅有與左右鄰居的本地互連。所有處理器可同時與鄰居進行比較、交換操作，交替以奇-偶、偶-奇的順序。該演算法由Habermann在1972年最初發表並展現了在並行處理上的效率。但在單處理器串列運行此演算法，類似冒泡排序，較為簡單但效率並不特別高。
實現代碼：
[cpp] view plain
void OddEvenSort(int *a, int len)
{
bool swapped = true;
while (swapped)
{
swapped = false;
for (int i=0; i<len-1; i=i+2)
{
if (a[i]>a[i+1])
{
swap(a[i], a[i+1]);
swapped = true;
}
}
for (int i=1; i<len-1; i=i+2)
{
if (a[i]>a[i+1])
{
swap(a[i], a[i+1]);
swapped = true;
}
}
}
}
（四）地精排序
最差時間復雜度：O(n^2)
最優時間復雜度：O(n)
平均時間復雜度：O(n^2)
穩定性：穩定
地精排序（Gnome Sort），被Dick Grune稱為最簡單的排序演算法。整個演算法只有一層循環，默認情況下前進冒泡，一旦遇到冒泡的情況發生就往回冒，直到把這個數字放好，然後繼續前進，前進到數組最後一個數結束。此排序演算法雖然代碼極短，但效率不高。
實現代碼：
[cpp] view plain
void GnomeSort(int *a, int len)
{
int i=0;
while (i<len)
{
if (i==0 || a[i-1]<=a[i]){
i++;
}
else {
swap(a[i], a[i-1]);
i--;
}
}
}
（五）快速排序
最差時間復雜度：O(n^2)
最優時間復雜度：O(nlogn)
平均時間復雜度：O(nlogn)
穩定性：不穩定
快速排序（Quick Sort），使用分治法策略來把一個串列分為兩個子串列，左邊子串的值總小於右邊的子串。此演算法的三個步驟：
1．分解：將數組A[l...r]劃分成兩個（可能空）子數組A[l...p-1]和A[p+1...r]，使得A[l...p-1]中的每個元素都小於等於A(p)，而且，小於等於A[p+1...r]中的元素。下標p也在這個劃分過程中計算。
2．解決：通過遞歸調用快速排序，對數組A[l...p-1]和A[p+1...r]排序。
3．合並：因為兩個子數組時就地排序，將它們的合並並不需要操作，整個數組A[l..r]已經排序。
實現代碼（其他實現方法見「三種快速排序演算法的實現」）：
[cpp] view plain
int partition(int* a, int left, int right)
{
int x = a[right];
int i = left-1, j = right;
for (;;)
{
while(a[++i] < x) { }
while(a[--j] > x) { if(j==left) break;}
if(i < j)
swap(a[i], a[j]);
else break;
}
swap(a[i],a[right]);
return i;
}
void quickSort(int* a, int left, int right)
{
if (left<right)
{
int p = partition(a, left, right);
quickSort(a, left, p-1);
quickSort(a, p+1, right);
}
}
（六）臭皮匠排序
最差時間復雜度：O(n^2.7)
臭皮匠排序（Stooge Sort），是一種低效的排序演算法，在《演算法導論》第二版第7章的思考題中被提到，是由Howard Fine等教授提出的所謂「漂亮的」排序演算法。將數列平分為三個子串，依次遞歸排序前兩個子串、後兩個子串、前兩個子串，最後確保整個數列有序。此演算法在最壞情況下的遞歸式為T(n) = 3T(2n/3) + 1。由主定理很容易知道它的演算法復雜性為：T(n) = O(n^log(3/2, 3))。很顯然log(3/2, 3))>2，也就是說這個演算法比插入排序的O(n^2)性能還差。
實現代碼：
[cpp] view plain
void StoogeSort(int *a, int i, int j)
{
if(a[i]>a[j])
swap(a[i], a[j]);
if((i+1)>=j)
return;
int k = (j-i+1)/3;
StoogeSort(a, i, j-k);
StoogeSort(a, i+k, j);
StoogeSort(a, i, j-k);
}
④ 如何生成一串數字的全排列 演算法
個人一點見解，希望對你有所幫助。
依我之見，你的對換部分出了一點點問題。只要作如下修改即可：
1、exchange 改為：
procere exchange(l,r:integer);
var
t,len:integer;
begin
if l=r then exit;
len:=r-l+1;
len:=len div 2;
for i:=1 to len do
begin
t:=a[l+i-1];
a[l+i-1]:=a[r-i+1];
a[r-i+1]:=t;
end;
end;
2、主過程中exchange(p,n)改為exchange(i+1,n)。
⑤ 頁面置換演算法的實驗
#include <stdio.h>
#define PROCESS_NAME_LEN 32 /*進程名稱的最大長度*/
#define MIN_SLICE 10 /*最小碎片的大小*/
#define DEFAULT_MEM_SIZE 1024 /*默認內存的大小*/
#define DEFAULT_MEM_START 0 /*默認內存的起始位置*/
/* 內存分配演算法 */
#define MA_FF 1
#define MA_BF 2
#define MA_WF 3
int mem_size=DEFAULT_MEM_SIZE; /*內存大小*/
int ma_algorithm = MA_FF; /*當前分配演算法*/
static int pid = 0; /*初始pid*/
int flag = 0; /*設置內存大小標志*/
struct free_block_type
{
int size;
int start_addr;
struct free_block_type *next;
};
struct free_block_type *free_block;
struct allocated_block
{
int pid;
int size;
int start_addr;
char process_name[PROCESS_NAME_LEN];
struct allocated_block *next;
};
struct allocated_block *allocated_block_head;
/*初始化空閑塊，默認為一塊，可以指定大小及起始地址*/
struct free_block_type* init_free_block(int mem_size)
{
struct free_block_type *fb;
fb=(struct free_block_type *)malloc(sizeof(struct free_block_type));
if(fb==NULL)
{
printf("No mem\n");
return NULL;
}
fb->size = mem_size;
fb->start_addr = DEFAULT_MEM_START;
fb->next = NULL;
return fb;
}
void display_menu()
{
printf("\n");
printf("1 - Set memory size (default=%d)\n", DEFAULT_MEM_SIZE);
printf("2 - Select memory allocation algorithm\n");
printf("3 - New process \n");
printf("4 - Terminate a process \n");
printf("5 - Display memory usage \n");
printf("0 - Exit\n");
}
/*設置內存的大小*/
int set_mem_size()
{
int size;
if(flag!=0)
{ /*防止重復設置*/
printf("Cannot set memory size again\n");
return 0;
}
printf("Total memory size =");
scanf("%d", &size);
if(size>0)
{
mem_size = size;
free_block->size = mem_size;
}
flag=1;
return 1;
}
/*Best-fit使用最小的能夠放下將要存放數據的塊，First-first使用第一個能夠放下將要存放數據的塊，Worst-fit使用最大的能夠放下將要存放數據的塊。*/
/* 設置當前的分配演算法 */
/*分區分配演算法(Partitioning Placement Algorithm)
*/
void set_algorithm()
{
int algorithm;
printf("\t1 - First Fit\n");/*首次適應演算法(FF)：。 */
printf("\t2 - Best Fit\n");/*最佳適應演算法(BF)： */
printf("\t3 - Worst Fit\n");
scanf("%d", &algorithm);
if(algorithm>=1 && algorithm <=3) ma_algorithm=algorithm;
/*按指定演算法重新排列空閑區鏈表*/
rearrange(ma_algorithm);
}
void swap(int* data_1,int* data_2)
{
int temp;
temp=*data_1;
*data_1=*data_2;
*data_2=temp;
}
void rearrange_FF()
{
struct free_block_type *tmp, *work;
printf("Rearrange free blocks for FF \n");
tmp = free_block;
while(tmp!=NULL)
{
work = tmp->next;
while(work!=NULL)
{
if( work->start_addr < tmp->start_addr)
{ /*地址遞增*/
swap(&work->start_addr, &tmp->start_addr);
swap(&work->size, &tmp->size);
}
else
{
work=work->next;
}
}
tmp=tmp->next;
}
}
/*按BF演算法重新整理內存空閑塊鏈表(未完成)
void rearrange_BF()
{
struct free_block_type *tmp,*work;
printf("Rearrange free blocks for BF\n");
tmp=free_block;
while(tmp!=NULL)
{
work=tmp->next;
while(work!=NULL)
{
}
}
}
*/
/*按WF演算法重新整理內存空閑塊鏈表(未完成)
void rearrange_WF()
{
struct free_block_type *tmp,*work;
printf("Rearrange free blocks for WF \n");
tmp=free_block;
while(tmp!=NULL)
{
work=tmp->next;
while(work!=NULL)
{
}
}
}
*/
/*按指定的演算法整理內存空閑塊鏈表*/
int rearrange(int algorithm)
{
switch(algorithm)
{
case MA_FF: rearrange_FF(); break;
/*case MA_BF: rearrange_BF(); break; */
/*case MA_WF: rearrange_WF(); break; */
}
}
/*創建新的進程，主要是獲取內存的申請數量*/
int new_process()
{
struct allocated_block *ab;
int size;
int ret;
ab=(struct allocated_block *)malloc(sizeof(struct allocated_block));
if(!ab)
exit(-5);
ab->next = NULL;
pid++;
sprintf(ab->process_name, "PROCESS-%02d", pid);
ab->pid = pid;
printf("Memory for %s:", ab->process_name);
scanf("%d", &size);
if(size>0) ab->size=size;
ret = allocate_mem(ab); /* 從空閑區分配內存，ret==1表示分配ok*/
/*如果此時allocated_block_head尚未賦值，則賦值*/
if((ret==1) &&(allocated_block_head == NULL))
{
allocated_block_head=ab;
return 1;
}
/*分配成功，將該已分配塊的描述插入已分配鏈表*/
else if (ret==1)
{
ab->next=allocated_block_head;
allocated_block_head=ab;
return 2;
}
else if(ret==-1)
{ /*分配不成功*/
printf("Allocation fail\n");
free(ab);
return -1;
}
return 3;
}
/*分配內存模塊*/
int allocate_mem(struct allocated_block *ab)
{
struct free_block_type *fbt,*pre,*r;
int request_size=ab->size;
fbt=pre=free_block;
while(fbt!=NULL)
{
if(fbt->size>=request_size)
{
if(fbt->size-request_size>=MIN_SLICE)
{
fbt->size=fbt->size-request_size;
}
/*分配後空閑空間足夠大，則分割*/
else
{
r=fbt;
pre->next=fbt->next;
free(r);
/*分割後空閑區成為小碎片，一起分配*/
return 1;
}
}
pre = fbt;
fbt = fbt->next;
}
return -1;
}
/*將ab所表示的已分配區歸還，並進行可能的合並*/
int free_mem(struct allocated_block *ab)
{
int algorithm = ma_algorithm;
struct free_block_type *fbt, *pre, *work;
fbt=(struct free_block_type*) malloc(sizeof(struct free_block_type));
if(!fbt)
return -1;
fbt->size = ab->size;
fbt->start_addr = ab->start_addr;
/*插入到空閑區鏈表的頭部並將空閑區按地址遞增的次序排列*/
fbt->next = free_block;
free_block=fbt;
rearrange(MA_FF);
fbt=free_block;
while(fbt!=NULL)
{
work = fbt->next;
if(work!=NULL)
{
/*如果當前空閑區與後面的空閑區相連，則合並*/
if(fbt->start_addr+fbt->size == work->start_addr)
{
fbt->size += work->size;
fbt->next = work->next;
free(work);
continue;
}
}
fbt = fbt->next;
}
rearrange(algorithm); /*重新按當前的演算法排列空閑區*/
return 1;
}
/*?釋放ab數據結構節點*/
int dispose(struct allocated_block *free_ab)
{
struct allocated_block *pre, *ab;
if(free_ab == allocated_block_head)
{ /*如果要釋放第一個節點*/
allocated_block_head = allocated_block_head->next;
free(free_ab);
return 1;
}
pre = allocated_block_head;
ab = allocated_block_head->next;
while(ab!=free_ab)
{
pre = ab;
ab = ab->next;
}
pre->next = ab->next;
free(ab);
return 2;
}
/*查找要刪除的進程*/
struct allocated_block* find_process(int pid)
{
struct allocated_block *temp;
temp=allocated_block_head;
while(temp!=NULL)
{
if(temp->pid==pid)
{
return temp;
}
temp=temp->next;
}
}
/*刪除進程，歸還分配的存儲空間，並刪除描述該進程內存分配的節點*/
void kill_process()
{
struct allocated_block *ab;
int pid;
printf("Kill Process, pid=");
scanf("%d", &pid);
ab=find_process(pid);
if(ab!=NULL)
{
free_mem(ab); /*釋放ab所表示的分配區*/
dispose(ab); /*釋放ab數據結構節點*/
}
}
/* 顯示當前內存的使用情況，包括空閑區的情況和已經分配的情況 */
int display_mem_usage()
{
struct free_block_type *fbt=free_block;
struct allocated_block *ab=allocated_block_head;
if(fbt==NULL) return(-1);
printf("----------------------------------------------------------\n");
/* 顯示空閑區 */
printf("Free Memory:\n");
printf("%20s %20s\n", " start_addr", " size");
while(fbt!=NULL)
{
printf("%20d %20d\n", fbt->start_addr, fbt->size);
fbt=fbt->next;
}
/* 顯示已分配區 */
printf("\nUsed Memory:\n");
printf("%10s %20s %10s %10s\n", "PID", "ProcessName", "start_addr", " size");
while(ab!=NULL)
{
printf("%10d %20s %10d %10d\n", ab->pid, ab->process_name, ab->start_addr, ab->size);
ab=ab->next;
}
printf("----------------------------------------------------------\n");
return 0;
}
**********************************************************************
樓主啊，小女子給你的是殘缺版滴，要是你給我分，我就把剩下滴給你,上次在北京大學貼吧都被人騙了，世道炎涼啊O(∩_∩)O~
⑥ 常見的排序演算法—選擇，冒泡，插入，快速，歸並
太久沒看代碼了，最近打算復習一下java，又突然想到了排序演算法，就把幾種常見的排序演算法用java敲了一遍，這里統一將無序的序列從小到大排列。
選擇排序是一種簡單直觀的排序演算法。它的工作原理是：第一次從待排序的數據元素中選出最小的一個元素，存放在序列的起始位置，然後再從剩餘的未排序元素中尋找到最小元素，繼續放在下一個位置，直到待排序元素個數為0。
選擇排序代碼如下：
public void Select_sort(int[] arr) {
int temp,index;
for( int i=0;i<10;i++) {
index = i;
for(int j = i + 1 ; j < 10 ; j++) {
if(arr[j] < arr[index])
index = j;
}
/*
temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
*/
swap(arr,i,index);
}
System.out.print("經過選擇排序後：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr[i] +" ");
System.out.println("");
}
冒泡排序是一種比較基礎的排序演算法，其思想是相鄰的元素兩兩比較，較大的元素放後面，較小的元素放前面，這樣一次循環下來，最大元素就會歸位，若數組中元素個數為n，則經過（n-1）次後，所有元素就依次從小到大排好序了。整個過程如同氣泡冒起，因此被稱作冒泡排序。
選擇排序代碼如下：
public void Bubble_sort(int[] arr) {
int temp;
for(int i = 0 ; i < 9 ; i++) {
for(int j = 0 ; j < 10 - i - 1 ;j++) {
if(arr[j] > arr[j+1]) {
/*
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
*/
swap(arr,j,j+1);
}
}
}
System.out.print("經過冒泡排序後：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr[i] +" ");
System.out.println("");
}
插入排序也是一種常見的排序演算法，插入排序的思想是：創建一個與待排序數組等大的數組，每次取出一個待排序數組中的元素，然後將其插入到新數組中合適的位置，使新數組中的元素保持從小到大的順序。
插入排序代碼如下：
public void Insert_sort(int[] arr) {
int length = arr.length;
int[] arr_sort = new int[length];
int count = 0;
for(int i = 0;i < length; i++) {
if(count == 0) {
arr_sort[0] = arr[0];
}else if(arr[i] >= arr_sort[count - 1]) {
arr_sort[count] = arr[i];
}else if(arr[i] < arr_sort[0]) {
insert(arr,arr_sort,arr[i],0,count);
}else {
for(int j = 0;j < count - 1; j++) {
if(arr[i] >= arr_sort[j] && arr[i] < arr_sort[j+1]) {
insert(arr,arr_sort,arr[i],j+1,count);
break;
}
}
}
count++;
}
System.out.print("經過插入排序後：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr_sort[i] +" ");
System.out.println("");
}
public void insert(int[] arr,int[] arr_sort,int value,int index,int count) {
for(int i = count; i > index; i--)
arr_sort[i] = arr_sort[i-1];
arr_sort[index] = value;
}
快速排序的效率比冒泡排序演算法有大幅提升。因為使用冒泡排序時，一次外循環只能歸位一個值，有n個元素最多就要執行（n-1）次外循環。而使用快速排序時，一次可以將所有元素按大小分成兩堆，也就是平均情況下需要logn輪就可以完成排序。
快速排序的思想是：每趟排序時選出一個基準值（這里以首元素為基準值），然後將所有元素與該基準值比較，並按大小分成左右兩堆，然後遞歸執行該過程，直到所有元素都完成排序。
public void Quick_sort(int[] arr, int left, int right) {
if(left >= right)
return ;
int temp,t;
int j = right;
int i = left;
temp = arr[left];
while(i < j) {
while(arr[j] >= temp && i < j)
j--;
while(arr[i] <= temp && i < j)
i++;
if(i < j) {
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
arr[left] = arr[i];
arr[i] = temp;
Quick_sort(arr,left, i - 1);
Quick_sort(arr, i + 1, right);
}
歸並排序是建立在歸並操作上的一種有效的排序演算法，歸並排序對序列的元素進行逐層折半分組，然後從最小分組開始比較排序，每兩個小分組合並成一個大的分組，逐層進行，最終所有的元素都是有序的。
public void Mergesort(int[] arr,int left,int right) {
if(right - left > 0) {
int[] arr_1 = new int[(right - left)/2 + 1];
int[] arr_2 = new int[(right - left + 1)/2];
int j = 0;
int k = 0;
for(int i = left;i <= right;i++) {
if(i <= (right + left)/2) {
arr_1[j++] = arr[i];
}else {
arr_2[k++] = arr[i];
}
}
Mergesort(arr_1,0,(right - left)/2);
Mergesort(arr_2,0,(right - left - 1)/2);
Merge(arr_1,arr_2,arr);
}
}
public void Merge(int[] arr_1,int[] arr_2,int[] arr) {
int i = 0;
int j = 0;
int k = 0;
int L1 = arr_1.length;
int L2 = arr_2.length;
while(i < L1 && j < L2) {
if(arr_1[i] <= arr_2[j]) {
arr[k] = arr_1[i];
i++;
}else {
arr[k] = arr_2[j];
j++;
}
k++;
}
if(i == L1) {
for(int t = j;j < L2;j++)
arr[k++] = arr_2[j];
}else {
for(int t = i;i < L1;i++)
arr[k++] = arr_1[i];
}
}
歸並排序這里我使用了left，right等變數，使其可以通用，並沒有直接用數字表示那麼明確，所以給出相關偽代碼，便於理解。
Mergesort(arr[0...n-1])
//輸入：一個可排序數組arr[0...n-1]
//輸出：非降序排列的數組arr[0...n-1]
if n>1
arr[0...n/2-1] to arr_1[0...(n+1)/2-1]//確保arr_1中元素個數>=arr_2中元素個數
//對於總個數為奇數時，arr_1比arr_2中元素多一個；對於總個數為偶數時，沒有影響
arr[n/2...n-1] to arr_2[0...n/2-1]
Mergesort(arr_1[0...(n+1)/2-1])
Mergesort(arr_2[0...n/2-1])
Merge(arr_1,arr_2,arr)
Merge(arr_1[0...p-1],arr_2[0...q-1],arr[0...p+q-1])
//輸入：兩個有序數組arr_1[0...p-1]和arr_2[0...q-1]
//輸出：將arr_1與arr_2兩數組合並到arr
int i<-0;j<-0;k<-0
while i
<p span="" do<="" jif arr_1[i] <= arr_2[j]
arr[k] <- arr_1[i]
i<-i+1
else arr[k] <- arr_2[j];j<-j+1
k<-k+1
if i=p
arr_2[j...q-1] to arr[k...p+q-1]
else arr_1[i...p-1] to arr[k...p+q-1]
package test_1;
import java.util.Scanner;
public class Test01 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] arr_1 = new int[10];
for(int i = 0 ; i < 10 ; i++)
arr_1[i] = sc.nextInt();
Sort demo_1 = new Sort();
//1~5一次只能運行一個，若多個同時運行，則只有第一個有效，後面幾個是無效排序。因為第一個運行的已經將帶排序數組排好序。
demo_1.Select_sort(arr_1);//-----------------------1
//demo_1.Bubble_sort(arr_1);//---------------------2
/* //---------------------3
demo_1.Quick_sort(arr_1, 0 , arr_1.length - 1);
System.out.print("經過快速排序後：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr_1[i] +" ");
System.out.println("");
*/
//demo_1.Insert_sort(arr_1);//--------------------4
/* //--------------------5
demo_1.Mergesort(arr_1,0,arr_1.length - 1);
System.out.print("經過歸並排序後：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr_1[i] +" ");
System.out.println("");
*/
}
}
class Sort {
public void swap(int arr[],int a, int b) {
int t;
t = arr[a];
arr[a] = arr[b];
arr[b] = t;
}
public void Select_sort(int[] arr) {
int temp,index;
for( int i=0;i<10;i++) {
index = i;
for(int j = i + 1 ; j < 10 ; j++) {
if(arr[j] < arr[index])
index = j;
}
/*
temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
*/
swap(arr,i,index);
}
System.out.print("經過選擇排序後：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr[i] +" ");
System.out.println("");
}
public void Bubble_sort(int[] arr) {
int temp;
for(int i = 0 ; i < 9 ; i++) {
for(int j = 0 ; j < 10 - i - 1 ;j++) {
if(arr[j] > arr[j+1]) {
/*
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
*/
swap(arr,j,j+1);
}
}
}
System.out.print("經過冒泡排序後：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr[i] +" ");
System.out.println("");
}
public void Quick_sort(int[] arr, int left, int right) {
if(left >= right)
return ;
int temp,t;
int j = right;
int i = left;
temp = arr[left];
while(i < j) {
while(arr[j] >= temp && i < j)
j--;
while(arr[i] <= temp && i < j)
i++;
if(i < j) {
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
arr[left] = arr[i];
arr[i] = temp;
Quick_sort(arr,left, i - 1);
Quick_sort(arr, i + 1, right);
}
public void Insert_sort(int[] arr) {
int length = arr.length;
int[] arr_sort = new int[length];
int count = 0;
for(int i = 0;i < length; i++) {
if(count == 0) {
arr_sort[0] = arr[0];
}else if(arr[i] >= arr_sort[count - 1]) {
arr_sort[count] = arr[i];
}else if(arr[i] < arr_sort[0]) {
insert(arr,arr_sort,arr[i],0,count);
}else {
for(int j = 0;j < count - 1; j++) {
if(arr[i] >= arr_sort[j] && arr[i] < arr_sort[j+1]) {
insert(arr,arr_sort,arr[i],j+1,count);
break;
}
}
}
count++;
}
System.out.print("經過插入排序後：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr_sort[i] +" ");
System.out.println("");
}
public void insert(int[] arr,int[] arr_sort,int value,int index,int count) {
for(int i = count; i > index; i--)
arr_sort[i] = arr_sort[i-1];
arr_sort[index] = value;
}
public void Mergesort(int[] arr,int left,int right) {
if(right - left > 0) {
int[] arr_1 = new int[(right - left)/2 + 1];
int[] arr_2 = new int[(right - left + 1)/2];
int j = 0;
int k = 0;
for(int i = left;i <= right;i++) {
if(i <= (right + left)/2) {
arr_1[j++] = arr[i];
}else {
arr_2[k++] = arr[i];
}
}
Mergesort(arr_1,0,(right - left)/2);
Mergesort(arr_2,0,(right - left - 1)/2);
Merge(arr_1,arr_2,arr);
}
}
public void Merge(int[] arr_1,int[] arr_2,int[] arr) {
int i = 0;
int j = 0;
int k = 0;
int L1 = arr_1.length;
int L2 = arr_2.length;
while(i < L1 && j < L2) {
if(arr_1[i] <= arr_2[j]) {
arr[k] = arr_1[i];
i++;
}else {
arr[k] = arr_2[j];
j++;
}
k++;
}
if(i == L1) {
for(int t = j;j < L2;j++)
arr[k++] = arr_2[j];
}else {
for(int t = i;i < L1;i++)
arr[k++] = arr_1[i];
}
}
}
若有錯誤，麻煩指正，不勝感激。