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

快速選擇SELECT算法的實現

本節,咱們將依據下圖所示的步驟,采取中位數的中位數選取樞紐元的方法來實現此SELECT算法,

不過,在實現之前,有個細節我還是必須要提醒你,即上文中2.2節開頭處所述,“數組元素索引是從“0...i”開始計數的,所以第k小的元素應該是返回a[i]=a[k-1].即k-1=i。換句話就是說,第k小元素,實際上應該在數組中對應下標為k-1”這句話,我想,你應該明白了:返回數組中第k小的元素,實際上就是返回數組中的元素array[i],即array[k-1]。ok,最後請看此快速選擇SELECT算法的完整代碼實現(據我所知,在此之前,從沒有人采取中位數的中位數選取樞紐元的方法來實現過這個SELECT算法):

//copyright@ yansha && July && 飛羽 
//July、updated,2011.05.19.清晨。 
//版權所有,引用必須注明出處:http://www.linuxidc.com。 
#include <iostream> 
#include <time.h> 
using namespace std; 
 
const int num_array = 13; 
const int num_med_array = num_array / 5 + 1; 
int array[num_array]; 
int midian_array[num_med_array]; 
 
//冒泡排序(晚些時候將修正為插入排序) 
/*void insert_sort(int array[], int left, int loop_times, int compare_times)
{
    for (int i = 0; i < loop_times; i++)
    {
        for (int j = 0; j < compare_times - i; j++)
        {
            if (array[left + j] > array[left + j + 1])
                swap(array[left + j], array[left + j + 1]);
        }
    }
}*/ 
 
/*
//插入排序算法偽代碼
INSERTION-SORT(A)                              cost    times
1  for j ← 2 to length[A]                      c1      n
2      do key ← A[j]                          c2      n - 1
3          Insert A[j] into the sorted sequence A[1 ‥ j - 1].    0...n - 1
4          i ← j - 1                          c4      n - 1
5          while i > 0 and A[i] > key          c5     
6            do A[i + 1] ← A[i]              c6     
7            i ← i - 1                        c7     
8          A[i + 1] ← key                      c8      n - 1
*/ 
//已修正為插入排序,如下: 
void insert_sort(int array[], int left, int loop_times) 

    for (int j = left; j < left+loop_times; j++) 
    { 
        int key = array[j]; 
        int i = j-1; 
        while ( i>left && array[i]>key ) 
        { 
            array[i+1] = array[i]; 
            i--; 
        } 
        array[i+1] = key; 
    } 

 
int find_median(int array[], int left, int right) 

    if (left == right) 
        return array[left]; 
     
    int index; 
    for (index = left; index < right - 5; index += 5) 
    { 
        insert_sort(array, index, 4); 
        int num = index - left; 
        midian_array[num / 5] = array[index + 2]; 
    } 
     
    // 處理剩余元素 
    int remain_num = right - index + 1; 
    if (remain_num > 0) 
    { 
        insert_sort(array, index, remain_num - 1); 
        int num = index - left; 
        midian_array[num / 5] = array[index + remain_num / 2]; 
    } 
     
    int elem_aux_array = (right - left) / 5 - 1; 
    if ((right - left) % 5 != 0) 
        elem_aux_array++; 
     
    // 如果剩余一個元素返回,否則繼續遞歸 
    if (elem_aux_array == 0) 
        return midian_array[0]; 
    else 
        return find_median(midian_array, 0, elem_aux_array); 

 
// 尋找中位數的所在位置 
int find_index(int array[], int left, int right, int median) 

    for (int i = left; i <= right; i++) 
    { 
        if (array[i] == median) 
            return i; 
    } 
    return -1; 

 
int q_select(int array[], int left, int right, int k) 

    // 尋找中位數的中位數 
    int median = find_median(array, left, right); 
     
    // 將中位數的中位數與最右元素交換 
    int index = find_index(array, left, right, median); 
    swap(array[index], array[right]); 
     
    int pivot = array[right]; 
     
    // 申請兩個移動指針並初始化 
    int i = left; 
    int j = right - 1;   
     
    // 根據樞紐元素的值對數組進行一次劃分 
    while (true) 
    {   
        while(array[i] < pivot) 
            i++; 
        while(array[j] > pivot) 
            j--; 
        if (i < j) 
            swap(array[i], array[j]); 
        else   
            break;   
    } 
    swap(array[i], array[right]); 
     
    /* 對三種情況進行處理:(m = i - left + 1)
    1、如果m=k,即返回的主元即為我們要找的第k小的元素,那麼直接返回主元a[i]即可;
    2、如果m>k,那麼接下來要到低區間A[0....m-1]中尋找,丟掉高區間;
    3、如果m<k,那麼接下來要到高區間A[m+1...n-1]中尋找,丟掉低區間。
    */ 
    int m = i - left + 1;     
    if (m == k) 
        return array[i]; 
    else if(m > k)   
        //上條語句相當於if( (i-left+1) >k),即if( (i-left) > k-1 ),於此就與2.2節裡的代碼實現一、二相對應起來了。 
        return q_select(array, left, i - 1, k);   
    else   
        return q_select(array, i + 1, right, k - m); 

 
int main() 

    //srand(unsigned(time(NULL))); 
    //for (int j = 0; j < num_array; j++) 
    //array[j] = rand(); 
     
    int array[num_array]={0,45,78,55,47,4,1,2,7,8,96,36,45}; 
    // 尋找第k最小數 
    int k = 4; 
    int i = q_select(array, 0, num_array - 1, k); 
    cout << i << endl; 
     
    return 0; 
}

Copyright © Linux教程網 All Rights Reserved