7种排序算法

7种排序算法

package com.org.momo.排序算法;public class Sort {  public static void displayData(int[] data) {  for (int d : data) {    System.out.print(d + " ");   }  System.out.println("");  }  /**   * 快速排序:时间复杂度O(nlogn)，最坏时间复杂度O(n2)，平均时间复杂度O(nlogn)，算法不具稳定性         思想:        基于冒泡排序,取第一个作为关键值a,用a与后面开始往前比较,遇到比a小       的则交换,依然乘此关键值为a,再用a与第一个数开始向后比较,遇到比a大的则       交换,最终的关键值将依然是最初的第一个元素的值,用此值将此无序序列分成两       部分,比它小的都在它前面,大的都在后面,然后用递归将前面和后面的分别用快       速排序进行处理,得到最终的有序序列.   */  public static void quickSort(int[] src, int begin, int end) {   if (begin < end) {    int key = src[begin];    int i = begin;    int j = end;     while (i < j) {     while (i < j && src[j] > key) {      j--;     }     if (i < j) {      src[i] = src[j];      i++;     }     while (i < j && src[i] < key) {      i++;     }     if (i < j) {      src[j] = src[i];      j--;     }   }    src[i] = key;   quickSort(src, begin, i - 1);    quickSort(src, i + 1, end);   }  }  /** * 冒泡排序算法：时间复杂度O(n2)，算法具有稳定性，堆排序和快速排序算法不具   有稳定性，即排序后相同元素的顺序会发生变化    思想:   n个数,将第一个和第二个进行比较,将大的放在第二个位置,再将第二个和第  三比较,大的放在第三个位置,依次向后比较,比较n-1次,将最大的放在最后(n的位  置),然后再从第一个开始比较,比较n-2次,这次把最大的放到第n-1个位置,然后再  来回比较.遵循第i次遍历就从第一个数开始比较n-i次,将最后的值放在第n-i+1  的位置.    */  public static void bubbleSort(int[] src) {   if (src.length > 0) {    int length = src.length;    for (int i = 1; i < length; i++) {     for (int j = 0; j < length - i; j++) {      if (src[j] > src[j + 1]) {       int temp = src[j];       src[j] = src[j + 1];       src[j + 1] = temp;      }     }    }   }  }    /**   * 插入排序:适用于少量数据的排序，时间复杂度O(n2)，是稳定的排序算法，原地排序   * 将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，  */  public static void insertSort(int[] a) {   int length = a.length;    for (int i = 1; i < length; i++) {    int temp = a[i];    int j = i;    for (; j > 0 && a[j - 1] > temp; j--) {     a[j] = a[j - 1];    }    a[j] = temp;   }  }   /**   * 归并排序算法:稳定排序，非原地排序，空间复杂度O(n)，时间复杂度O(nlogn)   * 将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。  * 然后再把有序子序列合并为整体有序序列。  */  public static void mergeSort(int a[], int low, int high) {   if (low < high) {    mergeSort(a, low, (low + high) / 2);    mergeSort(a, (low + high) / 2 + 1, high);    merge(a, low, (high + low) / 2, high);   }   }  /**   * 归并排序辅助方法，合并   */  private static void merge(int[] a, int low, int mid, int high) {   int[] b = new int[high - low + 1];   int s = low;   int t = mid + 1;   int k = 0;   while (s <= mid && t <= high) {    if (a[s] <= a[t])     b[k++] = a[s++];    else     b[k++] = a[t++];   }   while (s <= mid)    b[k++] = a[s++];   while (t <= high)    b[k++] = a[t++];   for (int i = 0; i < b.length; i++) {    a[low + i] = b[i];   }  } /**   * 选择排序:分为简单选择排序、树形选择排序(锦标赛排序)、堆排序 此算法为简单选择排序   * 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，  * 直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。  */  public static void selectSort(int[] a) {   int length = a.length;   for (int i = 0; i < length; i++) {    int minIndex = i;       for (int j = i + 1; j < a.length; j++) {     if (a[j] < a[minIndex]) {      minIndex = j;     }    }        if (minIndex != i) {     int temp = a[minIndex];     a[minIndex] = a[i];     a[i] = temp;     }   }  }   /**   * 希尔排序:先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成（n除以d1）个组。  * 所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，  * 取第二个增量d2<d1重复上述的分组和排序，  * 直至所取的增量dt=1(dt<dt-l<…<d2<d1)，  * 即所有记录放在同一组中进行直接插入排序为止。  */  public static void shellSort(int[] a) {   int temp;   for (int k = a.length / 2; k > 0; k /= 2) {    for (int i = k; i < a.length; i++) {     for (int j = i; j >= k; j -= k) {      if (a[j - k] > a[j]) {       temp = a[j - k];       a[j - k] = a[j];       a[j] = temp;      }     }    }   }  }  /**   * 堆排序:最坏时间复杂度O(nlog2n)，平均性能接近于最坏性能。由于建初始堆所需的比较次数多，故堆不适合记录较少的比较 堆排序为原地不稳定排序   */  public static void heapSort(int[] array) {   for (int i = 1; i < array.length; i++) {    makeHeap(array, i);   }     for (int i = array.length - 1; i > 0; i--) {    int temp = array[i];    array[i] = array[0];    array[0] = temp;    rebuildHeap(array, i);   }  }  /**   * 堆排序辅助方法---创建堆   */  private static void makeHeap(int[] array, int k) {   int current = k;   while (current > 0 && array[current] > array[(current - 1)  - 6 - 2]) {    int temp = array[current];    array[current] = array[(current - 1) / 2];    array[(current - 1) / 2] = temp;    current = (current - 1) / 2;   }  }  /**   * 堆排序辅助方法---堆的根元素已删除，末尾元素已移到根位置，开始重建   */  private static void rebuildHeap(int[] array, int size) {   int currentIndex = 0;   int right = currentIndex * 2 + 2;   int left = currentIndex * 2 + 1;   int maxIndex = currentIndex;   boolean isHeap = false;   while (!isHeap) {    if (left < size && array[currentIndex] < array[left]) {     maxIndex = left;    }    if (right < size && array[maxIndex] < array[right]) {     maxIndex = right;    }    if (currentIndex == maxIndex) {     isHeap = true;    } else {     int temp = array[currentIndex];     array[currentIndex] = array[maxIndex];     array[maxIndex] = temp;     currentIndex = maxIndex;     right = currentIndex * 2 + 2;     left = currentIndex * 2 + 1;    }   }  }   public static void main(String[] args) {   int data[] = { 2,8,-2,10,0,6,4};   //快速排序  Sort.displayData(data) ;  Sort.quickSort(data,0,data.length-1) ;  Sort.displayData(data) ;    /*  //2.冒泡排序  Sort.displayData(data);   Sort.bubbleSort(data);   Sort.displayData(data); */ }   }