关于排序之交换排序

交换排序 ：

包括冒泡排序，快速排序。

 

冒泡排序法 ： 该算法是专门针对已部分排序的数据进行排序的一种排序算法。如果在你的数据清单中只有一两个数据是乱序的话，用这种算法就是最快的排序算法。如果你的数据 清单中的数据是随机排列的，那么这种方法就成了最慢的算法了。因此在使用这种算法之前一定要慎重。这种算法的核心思想是扫描数据清单，寻找出现乱序的两个 相邻的项目。当找到这两个项目后，交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好。

 

 

关于冒泡排序，网上有好几种实现方法，在这里整理一下，方便以后自己复习：

第一种方法：

         源码：

package com.zhaozy.sort;

 

import java.util.Random;

 

/**

 * 冒泡排序

 *

 * @author zhaozy

 *

 */

public class MaopaoSort {

 

    public static void main(String[] args) {

 

       int [] dataset = new int [20];

       Random random = new Random();

       System. out .println( "Befor sorted:" );

       for ( int i = 0; i < dataset. length ; i++) {

           dataset[i] = ( int ) (random.nextDouble() * 100);

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

       }

       System. out .println();

       testMaopao (dataset);

    }

 

    public static void testMaopao( int [] dataset) {

       int temp = 0;

       for ( int i = 0; i < dataset. length ; i++) {

           for ( int j = 0; j < dataset. length - i - 1; j++) {

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

                  temp = dataset[j];

                  dataset[j] = dataset[j + 1];

                  dataset[j + 1] = temp;

              }

           }

       }

       printNum (dataset);

    }

    // 负责显示出排好序的数组

    public static void printNum( int [] dataset) {

       // StringBuffer result=new StringBuffer();

       String result = "" ;

       for ( int i = 0; i < dataset. length ; i++) {

           result += dataset[i] + " " ;

       }

       System. out .println( "After sorted:" );

       System. out .println(result);

    }

}

 

使用java.util.Random类取得随机数。

 

第二种实现方法：

         源码：

// 冒泡排序

    public void BubbleExchangeSort( double [] sorted) {

       int sortedLen = sorted. length ;

       for ( int j = sortedLen; j > 0; j--) {

           int end = j;

           for ( int k = 1; k < end - 1; k++) {

              double tempB = sorted[k];

              sorted[k] = sorted[k] < sorted[k + 1] ? sorted[k]

                     : sorted[k + 1];

              if (Math.abs (sorted[k] - tempB) > 10e-6) {

                  sorted[k + 1] = tempB;

              }

           }

       }

    }

 

在这里，也让自己加深了对Java方法中的参数传递是值传递的认识，即传递的是地址，如果传递的是一个对象，则此对象的地址不能改变，但是这个对象中的属性是可以改变的。

         就像在上面这个方法，参数传递的是sorted数组，数组中的单个值是可以改变的，这样，即使不将sorted数组作为返回值返回，得到的sorted数组其实里面的值已经改变了。

         不过我个人感觉可以做以下的修改：

/*if (Math.abs(sorted[k] - tempB) > 10e-6) {

                  sorted[k + 1] = tempB;

              }*/

          

               if (sorted[k]!=tempB){

                  sorted [k+1]=tempB;

              }

因为注释的内容我感觉是判断是否做过移动，如 45 ， 23 ，因为 45>23 ，所以 sorted[k] 由原先的 45 变为了 23 ，但是此时的 sorted[k+1] 还是 23 ，所以需要把 45 赋给 sorted[k+1], 所以只要判断一下 sorted[k] 和 tempB 的值是否一致就行了，而且这样还可以避免不稳定的情况出现。

 

快速排序 ： 通过一趟排序，将待排序记录分割成独立的两个部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个 序列有序。具体做法是：使用两个指针low,high, 初值分别设置为序列的头，和序列的尾，设置pivotkey为第一个记录，首先从high开始向前搜索第一个小于pivotkey的记录和 pivotkey所在位置进行交换，然后从low开始向后搜索第一个大于pivotkey的记录和此时pivotkey所在位置进行交换，重复知道 low=high了为止。

 

源码为：

package com.zhaozy.sort;

 

import java.util.Random;

 

/**

 * 快速排序

 *

 * @author zhaozy

 *

 */

public class QuickSort {

 

    public static void main(String[] args) {

 

       Random random = new Random();

 

       int [] dataset = new int [21];

       System. out .print( " 原始数据为： " );

//sorted[0]没有为其赋初值，值为0.0,其作用是作为临时数据存放的地方

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

           dataset[i] = ( int ) (random.nextDouble() * 100);

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

       }

 

       System. out .println();

 

       QuickSort sort = new QuickSort();

       sort.testQuick(dataset, 1, dataset. length - 1);

 

       System. out .print( " 排好序后的数据为： " );

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

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

       }

    }

 

    public void testQuick( int [] dataset, int low, int high) {

       if (low < high) {

           int pivot = this .findPivot(dataset, low, high);

           this .testQuick(dataset, low, pivot - 1);

           this .testQuick(dataset, pivot + 1, high);

       }

    }

 

    public int findPivot( int [] dataset, int low, int high) {

       dataset[0] = dataset[low];

       while (low < high) {

           while (low < high && dataset[high] >= dataset[0]) {

              --high;

           }

           dataset[low] = dataset[high];

           while (low < high && dataset[low] <= dataset[0]) {

              ++low;

           }

           dataset[high] = dataset[low];

       }

       dataset[low] = dataset[0];

       return low;

    }

}

 

在方法testQuick 中使用了递归的思想。

 

findPivot() 方法的另外一种实现方法：

private static int partition( int [] array, int low, int high) {

         int s = array[high];

         int i = low - 1;

         for ( int j = low; j < high; j++) {

             if (array[j] < s) {

                 i++;

                 swap (array, i, j);

             }

         }

         swap (array, ++i, high);

         return i;

     }

     // 掉位方法

     private static void swap( int [] array, int i, int j) {

         int temp;

         temp = array[i];

         array[i] = array[j];

         array[j] = temp ;

     }

 

有点晕，没看明白方法是怎么实现的，难道是自己现在的水平有限？呵呵，先做一下标记，以后继续研究。