빠 른 정렬 의 세 가지 실현 과 응용 장면

됐어, 쓸데없는 소리 하지 말고 바로 건어물 에 올 려.1. 빠 른 정렬 의 개념: 빠 른 정렬 (Quicksort) 은 거품 정렬 에 대한 개선 입 니 다.빠 른 순 서 는 C. A. R. Horno 가 1962 년 에 제출 했다.그의 기본 사상 은 한 번 의 정렬 을 통 해 정렬 할 데 이 터 를 독립 된 두 부분 으로 나 누 는 것 이다. 그 중에서 일부분 의 모든 데 이 터 는 다른 부분의 모든 데이터 보다 작다. 그 다음 에 이 방법 에 따라 이 두 부분의 데 이 터 를 각각 신속하게 정렬 하고 전체 정렬 과정 을 거 쳐 재 귀적 으로 진행 하여 전체 데 이 터 를 질서 있 는 서열 로 바 꿀 수 있다.2. 빠 른 정렬 의 세 가지 실현:

/*
way 1:Horno 
    ：
1、      key（       ），               ，       begin（     ） end（     ）
2、begin          key    （     ），end              （      ），
  ，  array[begin] array[end]，      。
3、 begin end  ， array[begin] array[end]      。*/
int partion1(int *array,int left,int right)
{
    int key = array[right];
    int begin = left;
    int end = right;
    while (beginwhile (beginarray[begin] <= key)//                        
                begin++;                    
        while (beginarray[end] >= key)    
                end--;  
        if (begin < end)
        std::swap(array[begin], array[end]);
    }
    if (begin!=right)//         ,             ，            ，    
    std::swap(array[begin], array[right]);
    return begin;
}
/*
way2:   
    ：
1、  begin end                   ，   key         ，array[end]         
2、begin     ，  key   ，    ， array[begin]   array[end]，  end    ，  begin      
3、end     ，  key   ，    ， array[end]   array[begin]，  begin    ，  end        
4、        ， begin end  ，     ， key        。
*/
int partion2(int *array, int left, int right)
{
    int key = array[right];
    int begin = left;
    int end = right;
    while (beginwhile (beginarray[begin] <= key)//                        
            begin++;
        if (begin < end)
        {
            array[end] = array[begin];
            end--;
        }   
        while (beginarray[end] >= key)//                      
            end--;
        if (beginarray[begin] = array[end];
            begin++;
        }       
    }
    if (begin != right)//         ,             ，            ，    
    std::swap(array[begin], array[end]);
    array[begin] = key;
    return begin;
}
/*
way3：     
    ：
1、       key，      pPre pPcur（pPre  pPcur      ），pPre pPcur   ，
 pPcur      key  ，  pPcur     （  pPre   ）， pPcur        pPre
  ，pPcur  ，    array[pPcur] array[pPre+1],  ，pPre     ，pPcur     。
2、 pCur    ，  pPre+1     key  。
*/
int partion3(int *array, int left, int right)
{
    int pPcur = left;
    int pPre = left-1;
    int key = array[right];
    while (pPcurif (array[pPcur ]< key)
        {
            swap(array[pPre + 1], array[pPcur]);
            pPre++;
        } 
        pPcur++;    
    }
    swap(array[right], array[++pPre]);
    return pPre;
}

void QuickSort(int *array,int left,int right )
{
    if (left < right)
    {
        int goal = partion2(array, left, right);
        QuickSort(array, left, goal-1);
        QuickSort(array, goal+1, right);
    }
}

3、       ：
//     ：
//          ，              ，       ，（         ，    ）
//             ，          :
int ThreeToMid(int a, int b, int c)//1  3  5
{
    if (a>b)
    {
        if (b > c)
            return b;
        else
        {
            if (a < c)
                return a;
            else
                return c;
        }
    }
    else
    {
        if (b < c)
            return b;
        else
        {
            if (a>c)
                return a;
            else
                return c;
        }
    }
}
4、    ：
（1）             （ ）  ，       （  ），     ，          ，                 。
（2）     （  ）    （  ）  ，       。
（3）                   n/2，             。
    ，                 O（N*logN），            O（N^2），         O（N*logN）。      O（1），   ，            。
         ，                ，    ，               。
5、    ：
                ------------     k   ------------
    arr    ：4,0,1,0,2,3，         1，            k   。
   ：
　　  STL            ，       k-1         k     ，             O(n*logn)。                     ，            k   ，    “      ”。               。
   ：
　　          ：         m      （          ， m = arr[0]），      ，                ：（1）m      （2）m  （3）m     。  m       m，m       m，    k             ， ：
a、 m         k，  k      m      ，          m         k   ；
b、 m         k，  k      m      ，          m         k-s   ，  s m       。

    ：
#include 
#define MAX_SIZE 100
int Biger[MAX_SIZE];
int Smaller[MAX_SIZE];

int Select_kth_Small(int arr[],int n,int k)
{
    if(n == 1)
        return arr[0];
    int b = 0,s = 0,t = arr[0],temp_n,temp_k;
    int temp[MAX_SIZE];
    for(int i = 1 ; i < n ; i++)//    
    {
        if(arr[i] > t)
            Biger[b++] = arr[i]; //       t ，        Biger[]
        else
            Smaller[s++] = arr[i];//      Smaller,      set[0]
    }
    if(b == 0)
    {
        Biger[b++] = t;//if...else       t              
    }
    else
    {
        Smaller[s++] = t;
    }
    //  Smaller          K，   K        
    //     Biger ，    Biger    k-r    
    //       
    if(s >= k)
    {
        temp_n = s;
        temp_k = k;
        for(i=0;ielse
    {
        temp_n = b;
        temp_k = k-s;
        for(i=0;ireturn Select_kth_Small(temp,temp_n,temp_k);
}

int main()
{
    int arr[]={4,0,1,0,2,3};
    int ans = Select_kth_Small(arr,6,3);
    cout<<"   arr[]={4,0,1,0,2,3} , 3    ："<return 0;
}