歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

排序總結之選擇式排序

一,直接選擇排序

介紹:直接選擇排序(Selection sort)是一種簡單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然後,再從剩余未排序元素中繼續尋找最小(大)元素,然後放到已排序序列的末尾。以此類推,直到所有元素均排序完畢。
選擇排序的主要優點與數據移動有關。如果某個元素位於正確的最終位置上,則它不會被移動。選擇排序每次交換一對元素,它們當中至少有一個將被移到其最終位置上,因此對n個元素的表進行排序總共進行至多n-1次交換。在所有的完全依靠交換去移動元素的排序方法中,選擇排序屬於非常好的一種。

復雜度分析:

數據結構 數組 最差時間復雜度 О(n²) 最優時間復雜度 О(n²) 平均時間復雜度 О(n²) 最差空間復雜度 О(n) total, O(1)auxiliary

選擇排序的交換操作介於0和(n-1)次之間。選擇排序的比較操作為n(n-1)/2次之間。選擇排序的賦值操作介於0和3(n-1)次之間。比較次數O(n^2),比較次數與關鍵字的初始狀態無關,總的比較次數N=(n-1)+(n-2)+...+1=n*(n-1)/2。 交換次數O(n),最好情況是,已經有序,交換0次;最壞情況是,逆序,交換n-1次。 交換次數比冒泡排序少多了,由於交換所需CPU時間比比較所需的CPU時間多,n值較小時,選擇排序比冒泡排序快。

java code:

private void select(int[] a) {
  for(int i=0;i<a.length-1;i++){
   int k=i;
   for (int j = i + 1; j < a.length; j++) {
    if (a[j] < a[k])
     k = j;
   }
   if (k != i) {
    int temp = a[i];
    a[i] = a[k];
    a[k] = temp;
   }
  }
 }

二,堆排序

介紹:(Heapsort)是指利用堆這種數據結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構,並同時滿足堆積的性質:即子結點的鍵值或索引總是小於(或者大於)它的父節點。

堆的操作:通常堆是通過一維數組來實現的。在堆的數據結構中,堆中的最大值總是位於根節點。堆中定義以下幾種操作:最大堆調整(Max_Heapify):將堆的末端子節點作調整,使得子節點永遠小於父節點;創建最大堆(Build_Max_Heap):將堆所有數據重新排序;堆排序(HeapSort):移除位在第一個數據的根節點,並做最大堆調整的遞歸運算。

堆排序的過程是:
1,創建一個堆H[0..n-1]
2,把堆首(最大值)和堆尾互換
3,把堆的尺寸縮小1,把新的數組頂端數據調整到相應位置
4,重復步驟2,直到堆的尺寸為1

復雜度分析:

數據結構 數組 最差時間復雜度 最優時間復雜度 平均時間復雜度 最差空間復雜度  total, auxiliary

java code:

import java.util.Arrays;

public class HeapSortDemo {
 // 堆排序是不穩定的排序方法
 private void heapSort(int[] a) {
  for (int i = (a.length - 1) / 2; i >= 0; i--) {
   siftDown(a, i, a.length - 1);//建堆
  }
  for (int i = a.length - 1; i >= 0; i--) {
   swap(a, 0, i);//交換堆頂元素到相應位置
   siftDown(a, 0, i - 1);
  }
 }
 //調整堆
 private void siftDown(int[] a, int left, int right) {
  int origin = a[left];
  int i = left, j = 2 * i + 1;
  while (j <= right) {
   if (j < right && a[j] < a[j + 1])
    j++;
   if (origin >= a[j])
    break;
   else {
    a[i] = a[j];
    i = j;
    j = 2 * j + 1;
   }
  }
  a[i] = origin;
 }
 private void swap(int[] a, int i, int j) {
  int temp = a[i];
  a[i] = a[j];
  a[j] = temp;
 }
 public static void main(String[] args) {
  int a[] = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62,
    99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51 };
  HeapSortDemo hsd = new HeapSortDemo();
  hsd.heapSort(a);
  System.out.println(Arrays.toString(a));
 }
}

Java編程思想(第4版) 中文清晰PDF完整版 http://www.linuxidc.com/Linux/2014-08/105403.htm

編寫高質量代碼 改善Java程序的151個建議 PDF高清完整版 http://www.linuxidc.com/Linux/2014-06/103388.htm

Java 8簡明教程 http://www.linuxidc.com/Linux/2014-03/98754.htm

Java對象初始化順序的簡單驗證 http://www.linuxidc.com/Linux/2014-02/96220.htm

Java對象值傳遞和對象傳遞的總結 http://www.linuxidc.com/Linux/2012-12/76692.htm

Copyright © Linux教程網 All Rights Reserved