dream.in.java

排序[原]

冒泡排序:

排序前: 11 5 8 1 2 12 0 19 2 4
第 1 次排序: 5 8 1 2 11 0 12 2 4 [19]
第 2 次排序: 5 1 2 8 0 11 2 4 [12 19]
第 3 次排序: 1 2 5 0 8 2 4 [11 12 19]
第 4 次排序: 1 2 0 5 2 4 [8 11 12 19]
第 5 次排序: 1 0 2 2 4 [5 8 11 12 19]
第 6 次排序: 0 1 2 2 [4 5 8 11 12 19] 此時(shí)已經(jīng)有序了,不會(huì)發(fā)生交換動(dòng)作,提前結(jié)束

平均復(fù)雜度為:O(n^2)

 

 選擇排序:
排序前: 8 5 1 9 9 11 9 18 4 10
第 1 次排序: [1] 5 8 9 9 11 9 18 4 10
第 2 次排序: [1 4] 8 9 9 11 9 18 5 10
第 3 次排序: [1 4] 5 9 9 11 9 18 8 10
第 4 次排序: [1 4 5] 8 9 11 9 18 9 10
第 5 次排序: [1 4 5 8 ]9 11 9 18 9 10
第 6 次排序: 1 4 5 8 9 9 11 18 9 10
第 7 次排序: 1 4 5 8 9 9 9 18 11 10
第 8 次排序: 1 4 5 8 9 9 9 10 11 18
第 9 次排序: 1 4 5 8 9 9 9 10 11 18
第 10 次排序: 1 4 5 8 9 9 9 10 11 18
Press any key to continue
平均復(fù)雜度為:O(n^2)

插入排序:
排序前: 4 14 7 5 16 11 2 18 8 2
第 1 次排序：4 14 7 5 16 11 2 18 8 2
第 2 次排序：4 7 14 5 16 11 2 18 8 2 把7插入到4后面
第 3 次排序：4 5 7 14 16 11 2 18 8 2
第 4 次排序：4 5 7 14 16 11 2 18 8 2
第 5 次排序：4 5 7 11 14 16 2 18 8 2
第 6 次排序：2 4 5 7 11 14 16 18 8 2
第 7 次排序：2 4 5 7 11 14 16 18 8 2
第 8 次排序：2 4 5 7 8 11 14 16 18 2
第 9 次排序：2 2 4 5 7 8 11 14 16 18
Press any key to continue


總結(jié):這三種排序算法是其它排序算法的基礎(chǔ),理解過(guò)程是非常主要的,然后加以推廣應(yīng)用.
測(cè)試代碼:

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define MAX 10

void  SWAP(int &x,int &y){
 int temp;
 temp = x;
 x = y;
 y =temp;
}
void bubSort(int[]);
void selSort(int[]);
void inSort(int []);
int main(){
 
 int number[MAX] ={0};
 int i;
 srand(time(NULL));
 printf("排序前: ");
 for(i = 0; i < MAX; i++){
  number[i] = rand() %20;
  printf("%d ", number[i]);
 }
 printf("\n");
 printf("\n選擇排序方式：\n"); 
 printf("(1)選擇排序\n(2)插入排序\n(3)冒泡排序\n:"); 
 scanf("%d", &i);   
 switch(i) {        
 case 1:          
  selSort(number); break;      
 case 2:       
  inSort(number); break;
 case 3:     

  bubSort(number); break;    
    default:     
  printf("選項(xiàng)錯(cuò)誤(1..3)\n");  
 }
 return 0;
}

/*
按升序排序
*/
void bubSort(int number[]){
 int i, j, k, flag = 1; //用flag作一標(biāo)志,可以提高效率
 for(i = 0; (i < MAX -1) && (flag ==1); i++){   /*外循環(huán)控制排序的總趟數(shù)*/
  flag = 0;//把標(biāo)志位標(biāo)為0,如果沒(méi)有進(jìn)行內(nèi)排序,表示之后的i+1到MAX-1趟均是有序的,不用排列了
  for(j = 0; j <MAX - i - 1; j++){  /*內(nèi)循環(huán)控制一趟排序的進(jìn)行*/
   if(number[j] > number[j+1]){
    int temp = number[j+1];
    number[j+1] = number[j];
    number[j] =temp;
    flag = 1;  //發(fā)生交換后,把flag置為1
   }
  }
  
  printf("第 %d 次排序: ", i+1);
  for(k = 0; k < MAX; k++){
   printf("%d ", number[k]);
  }
  printf("\n");
  
 }
 
}
/*
選擇排序
將要排序的對(duì)象分作兩部分，一個(gè)是已經(jīng)排序的，一個(gè)是未排序的，在示排序中找一個(gè)最小的元素
然后把它追加到已排序的最后一個(gè)位置
*/
void selSort(int number[]){
 int i, j, k, m;
 for(i = 0; i < MAX; i++ ){
  m = i;  //記錄當(dāng)前最小數(shù)的下標(biāo)
  //一次遍列把最小的數(shù)的下標(biāo)找出來(lái)
  for(j = i +1 ; j < MAX; j++){
   if(number[j] < number[m] )
    m = j; //從開(kāi)始向末尾遍列,如果遇到比number[m]小的數(shù),把它的下標(biāo)記下來(lái)
  }
  //交換第i個(gè)和第m個(gè)元素
  if( i != m){
            int temp = number[i];
   number[i] = number[m];
   number[m] =temp;
  }
  printf("第 %d 次排序: ", i+1);
  for(k = 0; k < MAX; k++){
   printf("%d ", number[k]);
  }
  printf("\n");
  
 }
}

/*
  插入排序，就像玩撲克一樣，我們將牌分為兩堆，每次從后面的一堆牌中抽出
  最前端的牌，然后插入到前一堆牌的合適位置
*/

void inSort(int number[]){
 int i, j, k , temp;
 for(j = 1; j < MAX; j++){
  temp = number[j];//保存在抽取出來(lái)的元素
  i = j -1;
  while(temp < number[i]){
   number[i+1]=number[i];//元素往后移
   i--;
   if(i == -1)   //當(dāng)i==1時(shí),已經(jīng)到了數(shù)組的始端
    break;
  }
  number[i+1] = temp;
  printf("第 %d 次排序：", j);      
  for(k = 0; k < MAX; k++)        
   printf("%d ", number[k]);     
  printf("\n");
 }
}

posted on 2009-04-12 13:27 YXY 閱讀(173) 評(píng)論(0)  編輯  收藏