新一天的练习

[珠浩 杨]

昨天的练习让大家学习了最短路径，今天的任务是排序算法，不管如何希望大家先掌握冒泡，快速，选择这三种排序算法。然后明天照样这样交。最后希望大家还
能再将今天的最短路径复习一遍，或是完善它。
ok。

杨珠浩
2011年11月16日

[Andrew Chui]

参考《数据结构（C++语言描述）》朱战力编著，练习了冒泡，快速，选择三种排序。

附件有代码和截图，

冒泡排序：

package BubbleSort;

public class BubbleSort {

/**

* 2011-11-18

* edit by QWR

*/

public static void BubbleSort(final int a[]){

int i,j,flag = 1;

int temp;

int n = a.length;

for(i=1;i < n && flag==1;i++){

flag = 0;

for(j = 0;j < n-i ; j++){

if(a[j] > a[j+1]){

flag = 1;

temp = a[j];

a[j] = a[j+1];

a[j+1] = temp;

}

}

}

}

public static void main(String[] args) {

int a[] = {98,68,12,100,36,78,7,16,88,69,33,21};

System.out.println("Befor sort：");

for(int i=1;i<a.length;i++ ){

System.out.print(a[i]+" ," );

}

System.out.println();

BubbleSort(a);

System.out.println("After sort：");

for(int i=1;i<a.length;i++ ){

System.out.print(a[i]+" ," );

}

}

}

//---------------------------------------------------

快速排序：

package QuickSort;

public class QuickSort {

/**2011-11-19

* edit by QWR

*/

public static void QuickSort(int[] a, int low, int high) {

int i = low;

int j = high;

int temp  = a[low];

while(i < j){

while(i < j && temp <= a[j]){ j--; }

if( i < j){

a[i]  = a[j];

i++;

}

while( i <j){ i++; }

if(i < j){

a[j] = a[i];

j--;

}

}

a[i] = temp;

if(low <i){ QuickSort(a, low, i-1); }

if(i<high){ QuickSort(a, j+1, high);}

}

public static void main(String[] args) {

int a[] = {98,68,12,100,36,78,7,16,88,69,33,21};

System.out.println("Befor sort：");

for(int i=1;i<a.length;i++ ){

System.out.print(a[i]+" ," );

}

System.out.println();

QuickSort(a , 0, a.length-1);

System.out.println("After sort：");

for(int i=1;i<a.length;i++ ){

System.out.print(a[i]+" ," );

}

}

}

//-----------------------------------------

选择排序：

package SelectSort;

public class SelectSort {

/**

* 2011-11-19

* edit by QWR

*/

public static void SelectSort(int a[]){

int i , j , small;

int temp ;

int n = a.length;

for( i = 0; i < n-1; i++){

small = i; //设第i个数据元素关键字最小

for( j=i; j < n; j++){  //寻找关键字最小的数据元素

if(a[j] < a[small] ){

small = j; //记住最小的元素下标

}

}

if(small != i){ //当最小元素的下标不为i时交换元素

temp = a[i];

a[i] = a[small];

a[small] = temp;

}

}

}

public static void main(String[] args) {

int a[] = {98,68,12,100,36,78,7,16,88,69,33,21};

System.out.println("Befor sort：");

for(int i=1;i<a.length;i++ ){

System.out.print(a[i]+" ," );

}

System.out.println();

SelectSort(a);

System.out.println("After sort：");

for(int i=1;i<a.length;i++ ){

System.out.print(a[i]+" ," );

}

}

}

[杨珠浩]

呵呵。。。我自己都没上传。。。现在就上传个最简单的冒泡排序。

2011/11/16 珠浩 杨 <clear...@gmail.com>

[Qzi]

收到！

2011/11/20 杨珠浩 <clear...@gmail.com>

--
Your biological and technological distinctiveness will be added to our own. Resistance is futile.

[Qzi]

1.迟来的算法，这次加入了算法的时钟消耗的对比
2.同时是在vs2008 和 gcc都编译通过的代码
3.里面另外附上了makefile 的初级使用方法(一个*.doc).

------------------------------------------------------------------------------------------------
| System  | CentOS Linux release 6.0 (Final)
------------------------------------------------------------------------------------------------
| Cimpiler | gcc version 4.4.4 20100726 (Red Hat 4.4.4-13) (GCC)
------------------------------------------------------------------------------------------------


void quickSort(vector<int> &number ,int left ,int right) 
{//用引用解决传参问题，以下类似 
    if ( left < right ) 
    { 
        int i = Partion(number , left, right) ;  
        quickSort(number, left, i-1);   // 对左边进行递归  
        quickSort(number, i+1, right);  // 对右边进行递归   
    } 
} 
void quick_sort() 
{//快速排序测试程序 
    double start ,end ; 
    vector<int> v(orited);//直接用全局orited初始化v 
    start = clock() ; 
    quickSort(v,0,MAX-1); 
    end = clock(); 
    cout << "quick  sort cost : " << end - start << endl; 
} 


/************************************************************************/ 
/*        冒泡排序                                                      */ 
/************************************************************************/ 
void bubble_sort() 
{ 
    int i,j; 
    vector<int> v(orited); 
    double start ,end; 

    start = clock(); 
    for ( i=0 ; i< MAX ; i++) 
    { 
        for (j=i+1 ; j< MAX ; j++) 
        { 
            if (v[i] > v[j])//最小的往左冒泡 
            { 
                swap(v[i],v[j]); 
            } 
        } 
    } 
    end = clock(); 
    cout << "bubble sort cost : " <<  end - start << endl; 
} 
/************************************************************************/ 
/*      选择排序                                                        */ 
/************************************************************************/ 
void select_sort() 
{ 
    int i,j,min; 
    vector<int> v(orited); 
    double start ,end; 
    start = clock(); 
    for (i=0 ; i< MAX ; i++) 
    { 
        min = i ; 
        for (j=i+1 ; j<MAX ; j++) 
        { 
            if (v[j] < v[min]) 
                min = j; 
        } 
        if (min != i) 
            swap(v[i],v[min]); 
    } 
    end = clock(); 
    cout << "select sort cost : " <<  end - start << endl; 
} 

2011/11/23 Qzi <hotsea...@gmail.com>