교환 정렬 - 고전적 인 빠 른 정렬 알고리즘 총결산

시간 복잡 도, 평균 O (nlogn), 최 악의 O (n);
불안정한 알고리즘
1. 알고리즘 사상
    빠 른 정렬 은 C. R. A. Hoare 가 1962 년 에 제기 한 구분 교환 정렬 입 니 다. 이 는 분 치 전략 을 사용 하여 일반적으로 분 치 법 (Divide - and - ConquerMethod) 이 라 고 부 릅 니 다.
(1) 분 치 법의 기본 사상
    분 치 법의 기본 사상 은 원래 의 문 제 를 몇 개의 규모 가 더 작 지만 구조 가 원래 의 문제 와 비슷 한 서브 문제 로 분해 하 는 것 이다. 이런 서브 문 제 를 재 귀적 으로 풀 고 이 서브 문제 들 의 해 를 원래 의 문제 로 조합 하 는 것 이다.
(2) 빠 른 정렬 의 기본 사상
    현재 정렬 할 무질서 구역 을 R [low.. high] 로 설정 하고 분 치 법 을 이용 하여 빠 른 정렬 의 기본 사상 을 다음 과 같이 설명 할 수 있 습 니 다.
① 분해:
R [low. high] 에서 하나의 기록 을 기준 (Pivot) 으로 선택 하고 이 기준 으로 현재 무질서 구역 을 왼쪽, 오른쪽 두 개의 작은 하위 구간 R [low. pivotpos - 1) 과 R [pivotpos + 1.. high] 로 나 누 며 왼쪽 하위 구간 의 모든 기록 키 워드 를 기준 기록 보다 작 게 합 니 다 (pivot 로 기록 하 셔 도 됩 니 다).의 키워드 pivot. key, 오른쪽 하위 구간 에 기 록 된 모든 키 워드 는 pivot. key 보다 크 고, 기준 기록 pivot 는 정확 한 위치 (pivotpos) 에 있 으 며, 후속 정렬 에 참가 할 필요 가 없습니다.
주의:
    구분 의 관건 은 기준 기록 이 있 는 위치 pivotpos 를 요구 하 는 것 입 니 다. 구분 결 과 는 간단하게 (pivot = R [pivotpos] 주의) 로 표시 할 수 있 습 니 다.
    R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys
                  그 중 low ≤ pivotpos ≤ high.
② 구 해:
재 귀적 호출 을 통 해 왼쪽, 오른쪽 구간 R [low. pivotpos - 1] 과 R [pivotpos + 1. high] 을 빠르게 정렬 합 니 다.
③ 조합:
'풀이' 단계 의 두 재 귀 호출 이 끝 났 을 때 왼쪽, 오른쪽 두 개의 키 구간 에 순서 가 있 기 때 문 입 니 다. 빠 른 정렬 에 있어 '조합' 절 차 는 무엇 을 할 필요 가 없 으 며 빈 조작 으로 볼 수 있 습 니 다.
1. 무질서 한 배열 [3, 2, 4, 1, 5, 9]
a), 첫 번 째 항목 [3] 을 먼저 꺼 내 고,
[3] 순서대로 나머지 항목 과 비교 하면,
[3] 보다 작 으 면 [3] 앞 에, 둘, 하나 가 [3] 보다 작 으 니까 모두 [3] 앞 에.
[3] 보다 크 면 [3] 뒤에, 4, 5, 9 대 [3] 크게, [3] 뒤에.
한 번 줄 을 서 니 아래 가 이렇게 되 었 다.
정렬 전 3, 2, 4, 1, 5, 9.
정렬 후 2, 1, 3, 4, 5, 9.
b), 전반부 당 김 [21] 에 대한 빠 른 정렬 계속
반복 절차 a) [첫 번 째 항목 2 와 나머지 항목 비교] 다음 에 이렇게 됩 니 다.
정렬 전 2 1
정렬 후 12
전반부 정렬 완료.
c), 후반 당 김 [459] 에 대한 빠 른 정렬 계속
반복 절차 a) [첫 번 째 항목 4 와 나머지 항목 비교] 다음 에 이렇게 됩 니 다.
정렬 전 4, 5, 9.
정렬 후 4, 5, 9.
d), 후반 당 김 [59] 에 대한 빠 른 정렬 계속
반복 절차 a) [첫 번 째 항목 5 와 나머지 항목 비교] 다음 에 이렇게 됩 니 다.
정렬 전 59
정렬 후 59
d. 이 예 에서 무시 할 수 있 지만 뒤의 숫자 가 시간 에 비해 적지 않 은 순환 을 계속 해 야 합 니 다.
전반부 정렬 완료.
전체 정렬 도 완료:
정렬 전: [3, 2, 4, 1, 5, 9]
정렬 후: [1, 2, 3, 4, 5, 9]
2. 빠 른 정렬 알고리즘 QuickSort
  void QuickSort(SeqList R，int low，int high)
   {/ / 대 R [low.. high] 빠 른 정렬
     int pivotpos; / 구분 후의 기준 기록 위치
     if (low < high) {/ 구간 길이 가 1 보다 클 때 만 정렬 해 야 합 니 다.
        pivotpos = Partition (R, low, high); / R [low.. high] 를 구분 합 니 다.
        QuickSort (R, low, pivotpos - 1); / / 왼쪽 구간 재 귀적 정렬
        QuickSort (R, pivotpos + 1, high); / 오른쪽 구간 재 귀적 정렬
      }
    } //QuickSort
  주의:
    전체 파일 을 정렬 하기 위해 서 는 QuickSort (R, 1, n) 를 호출 하면 R [l. n] 에 대한 정렬 을 완성 할 수 있 습 니 다.
구체 적 인 알고리즘 구현:

   1: int partition(int R[], int low, int high)

   2: {// R[low..high]   

   3:     int pivot = R[low];

   4:     int tmp =0;

   5:  

   6: //    int i = low, j= high ;

   7: //    print(R+low,high-low+1);

   8:  

   9:     while(low < high)

  10:     {

  11:         while( low <high &&R[high] >= pivot)

  12:             --high ;

  13:         swap(R[low] ,R[high]);    

  14:  

  15:         while (low < high && R[low] <= pivot )

  16:             ++low;

  17:         swap(R[low] ,R[high]);        

  18:  

  19:         

  20:     }    

  21:  

  22:  

  23:     //print(R+i,j-i+1);

  24:     

  25:     return high;

  26: }

  27: void quick_sort_z(int R[] ,int low ,int high)

  28: { 

  29:     int pivot_pos; //           

  30:     if(low<high){  //        1     

  31:         pivot_pos = partition(R ,low, high); // R[low..high]   

  32:     //    cout<<pivot_pos <<endl;

  33:         quick_sort_z(R, low, pivot_pos-1); //        

  34:         quick_sort_z(R, pivot_pos+1, high);//        

  35:     }

  36: }

  37:  

  38: void quick_sort(int R[], int low, int high)

  39: {

  40:     quick_sort_z(R,low,high);

  41: }

 
다른 parion 알고리즘 구현: 마지막 요 소 를 기준 으로

   1: int partition_a(int data[],int lo,int hi) 

   2: {

   3:     int key=data[hi];  //       ，data[hi]   

   4:     int i=lo-1;

   5:     for(int j=lo;j<hi;j++)   /// ，j p    r-1，  r。

   6:     {

   7:         if(data[j]<=key)

   8:         {

   9:             i=i+1;

  10:             swap(data[i],data[j]);

  11:         }

  12:     }

  13:     swap(data[i+1],data[hi]);   

  14:     return i+1;

  15: }

전체 원본 코드 (VS 2010 컴 파일):

   1: // code-summary.cpp :              。

   2:  

   3: /**************************************************************************

   4:     * Copyright (c) 2013,  All rights reserved.

   5:     *         : code-summary.cpp

   6:     *         :

   7:     *           :       

   8:     * 

   9:     *         : Ver 1.0

  10:     *       :    

  11:     *         : 2013/05/10

  12:     *

  13:     *         : 

  14:     *        :

  15:     *         :  

  16:     *       : GNU General Public License GPLv3

  17: *************************************************************************/

  18: #include "stdafx.h"

  19:  

  20: #include <iostream>

  21: #include <random>

  22: #include <stdlib.h>

  23: using namespace std;

  24:  

  25: //    

  26:  

  27: void init(int a[], int len)

  28: {

  29:     int i =0;

  30:     for( i=0;  i<len ;i++)

  31:     {

  32:         a[i]= rand();

  33:     }

  34:     return ;    

  35: }

  36: void print(int *a, int len)

  37: {

  38:     int i =0;

  39:     for( i=0;  i<len; i++)

  40:     {

  41:         cout << a[i] <<'\t';

  42:     }

  43:     cout << endl;

  44:     return ;    

  45: }

  46: void swap(int &a, int &b)

  47: {

  48:     int tmp =a;

  49:     a = b;

  50:     b=tmp;

  51:     return ;

  52: }

  53: int partition(int R[], int low, int high)

  54: {// R[low..high]   

  55:     int pivot = R[low];

  56:     int tmp =0;

  57:  

  58: //    int i = low, j= high ;

  59: //    print(R+low,high-low+1);

  60:  

  61:     while(low < high)

  62:     {

  63:         while( low <high &&R[high] >= pivot)

  64:             --high ;

  65:         swap(R[low] ,R[high]);    

  66:  

  67:         while (low < high && R[low] <= pivot )

  68:             ++low;

  69:         swap(R[low] ,R[high]);        

  70:  

  71:         

  72:     }    

  73:  

  74:  

  75:     //print(R+i,j-i+1);

  76:     

  77:     return high;

  78: }

  79:  

  80: int partition_a(int data[],int lo,int hi) 

  81: {

  82:     int key=data[hi];  //       ，data[hi]   

  83:     int i=lo-1;

  84:     for(int j=lo;j<hi;j++)   /// ，j p    r-1，  r。

  85:     {

  86:         if(data[j]<=key)

  87:         {

  88:             i=i+1;

  89:             swap(data[i],data[j]);

  90:         }

  91:     }

  92:     swap(data[i+1],data[hi]);   

  93:     return i+1;

  94: }

  95:  

  96: void quickSort(int R[] ,int low ,int high)

  97: { 

  98:     int pivot_pos; //           

  99:     if(low<high){  //        1     

 100:         pivot_pos = partition(R ,low, high); // R[low..high]   

 101:     //    cout<<pivot_pos <<endl;

 102:         quickSort(R, low, pivot_pos-1); //        

 103:         quickSort(R, pivot_pos+1, high);//        

 104:     }

 105: }

 106:  

 107: void quickSort_a(int R[] ,int low ,int high)

 108: { 

 109:     int pivot_pos; //           

 110:     if(low<high){  //        1     

 111:         pivot_pos = partition_a(R ,low, high); // R[low..high]   

 112:         //    cout<<pivot_pos <<endl;

 113:         quickSort_a(R, low, pivot_pos-1); //        

 114:         quickSort_a(R, pivot_pos+1, high);//        

 115:     }

 116: }

 117: void quick_sort(int R[], int low, int high)

 118: {

 119:     quickSort(R,low,high);

 120: }

 121:  

 122: void quick_sort_a(int R[], int low, int high)

 123: {

 124:     quickSort_a(R,low,high);

 125: }

 126:  

 127:  

 128: int _tmain(int argc, _TCHAR* argv[])

 129: {

 130:     int *arr = new int[10];

 131:     init(arr, 10);

 132:     print(arr, 10);

 133:     quick_sort(arr,0,9);

 134:     print(arr, 10 );

 135:  

 136:     init(arr, 10);

 137:     print(arr, 10);

 138:     quick_sort_a(arr,0,9);

 139:     print(arr, 10 );

 140:  

 141:     system("pause");

 142:     return 0;

 143: }

 144:  

 
 
참고 자료:
http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.3.2.1.htm
http://www.cnblogs.com/kkun/archive/2011/11/23/2260270.html
http://blog.csdn.net/v_july_v/article/details/6262915