首页 > 代码库 > 索引排序
索引排序
索引排序
在排序时,若是数据非常复杂。对数据的移动显然是费时的。若把数据移动改为索引(或指针)移动。则降低了操作复杂度。索引排序。也叫地址排序,就是这样的排序思想。
索引含义
依据索引的含义不同,索引排序的算法上也主要分为两种。
一、index[i]为array[i]终于在有序序列中的位置。
二、index[i]为位置i上终于应存放元素的下标。即终于元素按array[index[0]]、array[index[1]]……有序。
一个实例
原序列 array: 17 19 23 21 38 5 33 22
下标:0 1 2 3 4 5 6 7
index1:1 2 5 3 7 0 6 4
index2:5 0 1 3 7 2 6 4
得到索引数组后,依据索引数组对元素进行重排,因为index含义不同,重排算法也不同。以下直接给出两种索引排序代码,代码中有具体凝视:
索引排序一
代码
#include<iostream> #include<iomanip> using namespace std; /* 索引排序一 index[i]是array[i]的终于下标 */ void IndexSort1(int array[], int n) { if (array && n > 1) { //创建索引数组 int *index = new int[n]; //初始化索引数组 int i, j; for (i = 0; i < n; i++) index[i] = i; //相似于插入排序。在插入比較的过程中不断地改动index数组 for (i = 1; i < n; i++) { j = i; while (j) { if (array[i] < array[j-1]) { index[i]--; index[j - 1]++; } j--; } } //打印索引数组 cout << "索引数组" << endl; for (i = 0; i < n; i++) cout << setw(4) << index[i]; cout << endl; //依据index数组。重排原序列 bool modified = true; while (modified) { modified = false; for (i = 0; i < n - 1; i++) { //假设不在位置上,则调整 if (index[i] != i) { modified = true; j = index[i]; swap(array[i], array[j]); index[i] = index[j]; index[j] = j; } } } //释放空间 delete[]index; } } //打印 void print(int array[], int n) { if(array && n>0) { int i; for (i = 0; i < n; i++) cout << setw(4) << array[i]; cout << endl; } } int main() { cout << "***索引排序***by David***\n"; int array[] = {17, 19, 23, 21, 38, 5, 33, 22}; int n = sizeof(array) / sizeof(array[0]); cout << "原序列\n"; print(array, n); cout << "索引排序一" << endl; IndexSort1(array, n); cout << "排序后" << endl; print(array, n); system("pause"); return 0; }
执行
索引排序二
代码
#include<iostream> #include<iomanip> using namespace std; /* 索引排序二 index[i]是array[i]中应该放置数据的下标 */ void IndexSort2(int array[], int n) { if (array && n > 1) { //创建索引数组 int *index = new int[n]; //初始化索引数组 int i, j; for (i = 0; i < n; i++) index[i] = i; //相似于插入排序,在插入比較的过程中不断地改动index数组 for (i = 0; i < n; i++) { j = i; while (j) { if (array[index[j]] < array[index[j - 1]]) swap(index[j], index[j - 1]); else break; j--; } } //打印索引数组 cout << "索引数组" << endl; for (i = 0; i < n; i++) cout << setw(4) << index[i]; cout << endl; //元素重排 int temp, k; for (i = 0; i < n; i++) { j = i; temp = array[i]; while (index[j] != i) { k = index[j]; array[j] = array[k]; index[j] = j; j = k; } array[j] = temp; index[j] = j; } //释放空间 delete[]index; } } //打印 void print(int array[], int n) { if(array && n>0) { int i; for (i = 0; i < n; i++) cout << setw(4) << array[i]; cout << endl; } } int main() { cout << "***索引排序***by David***\n"; int array[] = {17, 19, 23, 21, 38, 5, 33, 22}; int n = sizeof(array) / sizeof(array[0]); cout << "原序列\n"; print(array, n); cout << "索引排序二" << endl; IndexSort2(array, n); cout << "排序后" << endl; print(array, n); system("pause"); return 0; }
元素重排算法的详解
/* 元素重排 看似两重循环,则实际上的时间复杂度是线性的:O(n) 普通情况下。经过一次while循环,将有多个元素归位 */ int temp, k; for (i = 0; i < n; i++) { /* 加了这个推断后,while循环的后两条语句的运行得到优化 :当元素已在正确的位置,则不需回填 */ if (index[i] != i) { //下面的做法相似于“挖坑填数” j = i; temp = array[i]; while (index[j] != i) { k = index[j]; //元素归位 array[j] = array[k]; //索引归位 index[j] = j; //新的坑 j = k; } //元素归位 array[j] = temp; //索引归位 index[j] = j; } }
执行
转载请注明出处,本文地址:http://blog.csdn.net/zhangxiangdavaid/article/details/37889669
若有所帮助。顶一个哦。
专栏文件夹:
- 数据结构与算法
- c指针
索引排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。