在线看毛片网站电影-亚洲国产欧美日韩精品一区二区三区,国产欧美乱夫不卡无乱码,国产精品欧美久久久天天影视,精品一区二区三区视频在线观看,亚洲国产精品人成乱码天天看,日韩久久久一区,91精品国产91免费

    
    
    <address id="vxupu"><td id="vxupu"></td></address>

      <pre id="vxupu"><small id="vxupu"></small></pre>
      <dfn id="vxupu"></dfn>
      <div id="vxupu"><small id="vxupu"></small></div>
    1. 新聞中心

      EEPW首頁 > 嵌入式系統(tǒng) > 設(shè)計應(yīng)用 > 比較型排序算法總結(jié)

      比較型排序算法總結(jié)

      作者: 時間:2016-12-01 來源:網(wǎng)絡(luò) 收藏

      但是存在一個特殊情況,如果操作的數(shù)組只存在兩個數(shù)據(jù)時,這種劃分方法就存在一些問題,因為一開始兩個下標i,j就指向了相同的位置,這時候如果a[0]大于a[1] ,那么經(jīng)過上面的操作以后j = 0, i = 1,這時候的pivot應(yīng)該是放在a[1]處,但是根據(jù)上面的條件可知,集合劃分至少需要三個元素,但是我們可以比較樞紐元與當前a[j]的值,對于兩種情況下都滿足交換的條件就是a[j] < pivot,因此只要當這個條件滿足是就交換a[j]和a[0]。上述的操作我們稱之為集合劃分操作。

      int Partition(int *a, int left, int right)
      {
      /*采用第一個元素作為樞紐元*/
      int pivot = a[left];
      int i = left + 1;
      int j = right;

      /*只有一個元素,實際上不用進行任何操作,直接返回*/
      if(i > j)
      return j;

      /*實際上存在一個問題就是i== j,這時候數(shù)組有兩個值*/
      while(1)
      {
      /*跳過所有小于等于pivot的值,同時設(shè)置邊界條件*/
      while(a[i] <= pivot && i < right)
      ++ i ;
      /*跳過所有大于pivot的值,同時設(shè)置邊界條件*/
      while(pivot < a[j] && j > left)
      -- j ;
      /*******************************************
      *如果 i < j,則說明數(shù)組之間存在間隔
      *上面的條件全部不滿足則說明找到S1,S2需要交換的數(shù)
      *一般當存在相同的數(shù)時,會存在i == j,這時實際上
      *a[left] = a[j]
      *一般都會產(chǎn)生i > j,這種情況發(fā)生在i+1=j時的交換操作
      *交換操作完成以后i++,j--,使得i < j.
      *******************************************/
      if(i < j)
      swap(&a[i ],&a[j]);
      else
      break;
      }
      /******************************************************
      根據(jù)上面的分析實際上j下標指向的數(shù)數(shù)都是小于或者等于pivot的
      等于pivot時就不需要交換a[left]和a[j],只需要返回樞紐元應(yīng)該的位置即可,
      同時也解決了只有兩個數(shù)值的數(shù)組問題。
      *******************************************************/
      if(pivot > a[j])
      swap(&a[left],&a[j]);
      /*返回樞紐元應(yīng)該存在的位置*/
      return j;
      }

      /*傳統(tǒng)的快速排序算法*/
      void t_quickSort(int *a, int left, int right)
      {
      int i = 0;

      /*如果left小于right*/
      if(left < right)
      {
      /*找到樞紐元的位置,并劃分了兩個集合S1,S2*/
      i = Partition(a,left,right);
      /*S1集合排序*/
      t_quickSort(a, left , i - 1);
      /*S2集合排序*/
      t_quickSort(a, i + 1, right);
      }
      }

      但是這種方法存在一個比較嚴重的問題,就是如果當數(shù)組是一個已經(jīng)完成排序的情況,采用快速排序的時間復(fù)雜度將是災(zāi)難性的。此時的時間復(fù)雜度為O(N^2),也就是最壞的情況,為了解決這種問題,采用了其他的解決方案,改變樞紐元的選擇決策,采用隨機選取或者三值的中值作為樞紐元。樞紐元的選擇能避免有序數(shù)組的快速排序問題。還有就是當數(shù)組的長度較小時,采用插入法等常規(guī)方法的速度更快,而且如上面分析所示,劃分集合的問題至少需要三個元素,雖然上面的方法能夠解決只有兩個元素的情況,但是如果考慮不周全就很難解決??梢愿鶕?jù)長度來選擇具體的排序排序方法,也就是當長度小于10時采用插入法排序,而當大于10時就直接采用快速排序,這時候的注意事項就比較少,不用考慮數(shù)組長度是否為2等。采用改良型的快速排序算法如下所示。

      /*快速排序*/
      void insertionSort(int *a, int left, int right)
      {
      int i = 0, j = 0;
      int tmp = 0;
      if(left >= right)
      return;

      for( i = left + 1; i <= right; ++ i)
      {
      tmp = a[i];
      for(j = i; j > left && tmp < a[j - 1]; -- j)
      a[j] = a[j - 1];
      a[j] = tmp;
      }
      }

      /*數(shù)據(jù)交換*/
      void swap(int *a, int *b)
      {
      if(a != b)
      {
      *a = *a + *b;
      *b = *a - *b;
      *a = *a - *b;
      }
      }

      /*選擇合適的樞紐元函數(shù)*/
      int median(int *a, int left, int right)
      {
      int mid = (right + left) / 2;

      if(a[mid] < a[left])
      swap(&a[mid], &a[left]);
      if(a[right] < a[left])
      swap(&a[right], &a[left]);
      if(a[right] < a[mid])
      swap(&a[right], &a[mid]);

      swap(&a[mid],&a[right - 1]);

      return a[right - 1];
      }

      /*實現(xiàn)快速排序的實際函數(shù)*/
      void quickSort(int *a, int left, int right)
      {
      int i = left, j = right - 1;
      int pivot = 0;
      if(left + 10 <= right)
      {
      /*選擇樞紐元*/
      pivot = median(a,left,right);

      while(1)
      {
      /*找到大于pivot的下標*/
      while(a[++ i] <= pivot){}
      /*找到不大于pivot的下標*/
      while(a[--j] > pivot){}

      if(i < j)
      swap(&a[i],&a[j]);
      else
      break;
      }
      /*確定樞紐元的位置*/
      swap(&a[i],&a[right - 1]);
      quickSort(a,left,i - 1);
      quickSort(a,i + 1,right);
      }
      else/*小長度的數(shù)組采用插入法排序*/
      insertionSort(a, left,right);
      }

      void QuickSort(int *a, int size)
      {
      quickSort(a,0,size - 1);
      }

      時間復(fù)雜度的測試,首先測試有序數(shù)組的排序操作,測試代碼和算法效果如下所示:

      #define LEN 100000

      int main()
      {
      int i = 0;
      int a[LEN];
      int b[LEN];
      int c[LEN];
      int d[LEN];
      int e[LEN];
      clock_t _start, _end;
      double times = 0;

      srand((int)time(0));

      for(i = 0; i < LEN; ++ i)
      {
      a[i] = i;
      b[i] = a[i];
      c[i] = a[i];
      d[i] = a[i];
      e[i] = a[i];
      }

      _start = clock();
      TQuickSort(a,LEN);
      _end = clock();
      times = (double)(_end - _start)/CLOCKS_PER_SEC;
      printf("The QuickSort took %fs",times);
      _start = clock();
      QuickSort(b,LEN);
      _end = clock();
      times = (double)(_end - _start)/CLOCKS_PER_SEC;
      printf("The Changed QuickSort took %fs",times);
      #if 10
      _start = clock();
      MergeSort(c,LEN);
      _end = clock();
      times = (double)(_end - _start)/CLOCKS_PER_SEC;
      printf("The MergeSort took %fs",times);

      _start = clock();
      InsertionSort(d,LEN);
      _end = clock();
      times = (double)(_end - _start)/CLOCKS_PER_SEC;
      printf("The InsertionSort took %fs",times);

      _start = clock();
      heapSort(e,LEN);
      _end = clock();
      times = (double)(_end - _start)/CLOCKS_PER_SEC;
      printf("The heapSort took %fs",times);
      #endif
      return 0;
      }

      結(jié)果如下:

      [gong@Gong-Computer sort]$ ./quickSort
      The QuickSort took 12.850000s
      The Changed QuickSort took 0.000000s
      The MergeSort took 0.030000s
      The InsertionSort took 0.000000s
      The heapSort took 0.020000s

      從上面的實驗結(jié)果可知,當為有序數(shù)組時,快速排序的速度并不快,甚至是最慢的。插入排序反而是最快的方式。同時我們可以發(fā)現(xiàn)采用上面的改進的快速排序算法排序速度很快,并不像傳統(tǒng)的算法那么費時間。
      測試采用隨機數(shù)產(chǎn)生的數(shù)組進行排序時的實驗效果:

      [gong@Gong-Computer sort]$ ./quickSort
      The QuickSort took 0.020000s
      The Changed QuickSort took 0.010000s
      The MergeSort took 0.030000s
      The InsertionSort took 15.240000s
      The heapSort took 0.020000s

      從上面的結(jié)果可知,對于非有序的數(shù)組,快速排序的效果是非常好的,但是插入排序就非常的差勁啦。


      上一頁 1 2 下一頁

      關(guān)鍵詞: 比較型排序算

      評論


      技術(shù)專區(qū)

      關(guān)閉
      ×

      “芯”朋友见面大会
      珠海|11.14|泰克“芯”朋友见面大会珠海站|泰克带您从测试角度看半导体的整条产业链,快来报名抢位吧>>