快速选择SELECT算法的达成
发布时间：2021-12-11 10:35:47 所属栏目：教程 来源：互联网
导读：本节，咱们将依据下图所示的步骤，采取中位数的中位数选取枢纽元的方法来实现此SELECT算法， 不过，在实现之前，有个细节我还是必须要提醒你，即上文中2.2节开头处所述，数组元素索引是从0...i开始计数的，所以第k小的元素应该是返回a[i]=a[k-1].即k-1=i。换
|
本节，咱们将依据下图所示的步骤，采取中位数的中位数选取枢纽元的方法来实现此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; }  （编辑：开发网_开封站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
浙公网安备 33038102330459号