sortways.java

包含常见的排序方法,如冒泡,选择,插入,堆,快速排序等,解压后为.java文件,可用记事本打开源代码,供有一定数据结构基础的初学者分析使用.

public class SortWays
{
    static void swap(double[] a, int i, int j) { //交换数组中两个数
        double t;
        t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    static int Max(double a[], int n) { //在长度为n的数组中寻求最大的数的序号
        int pos = 0;
        for (int i = 1; i < n; i++)
            if (a[pos] < a[i])
                pos = i;
        return pos;
    }

    static void printArray(double a[]) { //输出数组，每行15个元素
        int i = 0;
        System.out.print("Result:   ");
        for (i = 0; i < a.length; i++) {
            if (i % 15 == 0 && i > 0)
                System.out.print("\n          ");
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }

    static void interchange(double m, double n) { //交换两个数的值
        double temp;
        temp = m;
        m = n;
        n = temp;
    }

    static void QuickSort(double[] pData,int[] pDataNum,int left,int right) {
 int i,j;
 int iTemp;
 double middle,strTemp;
 i = left;
 j = right;
 middle = pData[(left+right)/2];
 do{
   while((pData[i]<middle) && (i<right))
         i++;
   while((pData[j]>middle) && (j>left))
         j--;
    if(i<=j){
      strTemp = pData[i];
      pData[i] = pData[j];
      pData[j] = strTemp;

      iTemp = pDataNum[i];
      pDataNum[i] = pDataNum[j];
      pDataNum[j] = iTemp;

     i++;
     j--;
 }
}while(i<=j);//如果两边扫描的下标交错，就停止（完成一次）

if(left<j)
QuickSort(pData,pDataNum,left,j);

if(right>i)
QuickSort(pData,pDataNum,i,right);
}

    static void heapInitialize(double a[], int size)
 {// Initialize max heap to array

  for (int i = size/2; i >= 0; i--) {
     double y = a[i]; // root of subtree

     // find place to put y
     int c = 2*i; // parent of c is target
                  // location for y
     while (c <= size-1) {
        // heap[c] should be larger sibling
        if (c < size-1 &&a[c] > a[c+1]) c++;

        // can we put y in heap[c/2]?
        if (y <= a[c]) break;  // yes

        // no
        a[c/2] = a[c]; // move child up
        c *= 2; // move down a level
        }
     a[c/2] = y;
     }
}

 static void  deleteMax(double heap[],int size)
{// Set x to max element and delete
 // max element from heap.
   // check if heap is empty
   if (size ==0)
      // empty
;
   else{

   // restucture heap
   double y = heap[--size]; // last element

   // find place for y starting at root
   int i = 0,  // current node of heap
       ci = 1; // child of i
   while (ci <size) {
      // heap[ci] should be larger child of i
      if (ci < size -1&& heap[ci] > heap[ci+1]) ci++;

      // can we put y in heap[i]?
      if (y <= heap[ci]) break;   // yes

      // no
      heap[i] = heap[ci]; // move child up
      i = ci;             // move down a level
      ci *= 2;
      }
   heap[i] = y;
   }
}



    static void insertionSort(double a[]) { //插入排序
        int n = a.length;
        for (int i = 1; i < n; i++) {
            double t = a[i];
            int j;
            for (j = i - 1; j >= 0 && t < a[j]; j--)
                a[j + 1] = a[j];
            a[j + 1] = t;
        }
    }

    static void bubbleSort(double a[]) { //冒泡排序
        int n = a.length;
        for (int i = n - 1; i > 0; i--)
            for (int j = 0; j < i; j++)
                if (a[j] > a[j + 1])
                    swap(a, j + 1, j);
    }

    static void selectionSort(double a[]) { //选择排序
        int n = a.length;
        for (int size = n; size > 1; size--) {
            int j = Max(a, size);
            swap(a, j, size - 1);

        }
    }
    static void quickSort(double a []){//快速排序
        int l=a.length,i;
        int pDataNum[]=new int[l];
        for (i=0;i<l;i++)
           pDataNum[i]=i;
        QuickSort(a,pDataNum,0,l-1);
    }

static void heapSort(double a[]){//堆排序
  int n=a.length;
heapInitialize(a, n);
double []b=new double[ n];
for(int i=0;i<n;i++)
    b[i]=a[i];
for(int i=0;i<n;i++){
a[i]=b[0];
deleteMax(b,n-i);
}
}

}