引言
上篇文章的运行结果会返回一个特征重要性列表，表示了一个预测分类问题中，各变量对分类的贡献程度，为了方便，我们需要将重要性排序，从而直观看的哪些是重要的特征，哪些是不重要的，其次，为了提高效率，有时我们需要的是特征对应的索引，而不是特征具体的值，例如我们需要首先知道是几号特征最重要，其次才需要知道它的重要性占比是多少，所以这篇文章主要介绍排序算法和返回索引.
回顾
[ 0.01711044 0.00919911 0.07351338 0.15271884 0.05239271 0.03671487
0.0210451 0.14226094 0.01203942 0.07059542 0.02364601 0.03109124
0.05005074 0.03305065 0.02808322 0.02442624 0.02248264 0.06917138
0.07207685 0.02974831 0.02858248]这是上节返回的特征重要性表，共有21个特征，特征重要性已进行归一化，排序并返回索引得到的结果是：
重要特征排序(按索引从大到小): [3, 7, 2, 18, 9, 17, 4, 12, 5, 13, 11, 19, 20, 14, 15, 10, 16, 6, 0, 8, 1]最大的元素索引是[3]，对应0.1527，其次是[7]，对应的是0.1422，依次类推.
快速排序思想
快速排序的中心思想是递归，时间复杂度在O(N*logN)到O(N*N)之间，通过初始化一个列表值，以这个值为基准，也就是pivot，然后将列表分为两个部分，小于等于pivot的一部分Less，和大于pivot的一部分More，然后针对这两个部分，把这两个部分看做两个单独的list，重复之前的确定pivot，划分Less，More的过程，直到最终列表划分完毕，即列表长度小于等于1时，因为此时只有一个元素，已经不需要排序.下面简单实现一个快速排序.
1）初始数列[7,3,4,6,9,5,1,2,8]，按列表第一个位置即0索引为分界线，分为两部分.
2）分为比7小的一组和比7大的一组，分别对这两组的索引0，即数字3和1数字9为界限，递归划分.
3）左边部分是比3小的和比3大的，右边部分是比9小的和比9大的（没有比9大的了）.
4）再次递归，这次数组长度都很短了，再次递归，得到最后结果.
实现
这里我们使用三种方法实现快排返回索引，第一种是numpy自带的argsort()函数实现，剩下两种分别是基于列表和基于指针的快速排序，后面再介绍两种快速排序算法的不同.
1）argsort()方法：
argsort方法是numpy库自带的排序并返回索引的方法，下面实现一下：
import numpy as np #导入numpy库
#转换为array
example = np.array([0.01711044,0.00919911,0.07351338,0.15271884,0.05239271,0.03671487,
0.0210451 ,0.14226094,0.01203942,0.07059542,0.02364601,0.03109124,
0.05005074,0.03305065,0.02808322,0.02442624,0.02248264,0.06917138,
0.07207685,0.02974831,0.02858248])
importance_list = np.argsort(-example)#argsort()方法
print(importance_list)返回结果
[ 3 7 2 18 9 17 4 12 5 13 11 19 20 14 15 10 16 6 0 8 1]argsort()方法默认返回从小到大排序的索引，因为我们的问题是预测变量重要性从高到低，所以添加一个'-'号，负责翻转列表，类似列表的reverse()方法.
2）快速排序基于列表：
def quicksort_list(array):
if len(array) < 2:#基线条件，保证在一定程度退出递归，避免死循环
return array
else:
pivot = array[0]
less = [i for i in array[1:] if i <= pivot]#比pivot小的
rather = [i for i in array[1:] if i > pivot]#比pivot大的
return quicksort_list(less) + [pivot] + quicksort_list(rather)3）快速排序基于指针：
def quicksort(list,low,high):#递归主程序
if high > low:
k = divide_list(list,low,high)
quicksort(list,low,k-1)
quicksort(list,k+1,high)
def divide_list(list,low,high):#根据指针，分为一边大一边小
left = low#初始化左指针
right = high#初始化右指针
k = list[low]#初始值
while left < right:#不断比较改变指针位置
while list[left] <= k:
left = left + 1
while list[right] > k:
right = right - 1
if left < right:#指针停止前进后退时互换元素直到两边相遇
list[left],list[right] = list[right],list[left]
list[low] = list[right]#交换元素
list[right] = k#返回分界点
return right4）返回索引
def sort_index(list):
index = {}
for i in range(len(list)):
index[list[i]] = i
return indexsort_index()函数负责构建一个元素{值：索引}的字典，保存元素索引号
def sorted(list_sort):
index_of_list = sort_index(list_sort)
sorted = quick_sort(list_sort)
# print(sorted)
rank = []
for i in sorted:
rank.append(index_of_list[i])
print('重要特征排序(按索引从大到小):',list(reversed(rank)))
return rank[::-1]sorted()函数通过快排获得元素，并通过列表和字典将排序好的元素索引返回.通过这两个函数和上面任一个快速排序程序，即可实现argsort()的功能.
5）快排+返回索引
这里使用第一种快排加返回索引函数，实现返回索引的功能.另一种快排同理.
def quicksort(array):
if len(array) < 2:
return array
else:
pivot = array[0]
less = [i for i in array[1:] if i <= pivot]
rather = [i for i in array[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(rather)
def sort_index(list):
index = {}
for i in range(len(list)):
index[list[i]] = i
return index
def sorted(list_sort):
index_of_list = sort_index(list_sort)
sorted = quicksort(list_sort)
# print(sorted)
rank = []
for i in sorted:
rank.append(index_of_list[i])
print('大小排序(按索引从大到小):',list(reversed(rank)))
return rank[::-1]
importance = [0.01711044,0.00919911,0.07351338,0.15271884,0.05239271,0.03671487,
0.0210451 ,0.14226094,0.01203942,0.07059542,0.02364601,0.03109124,
0.05005074,0.03305065,0.02808322,0.02442624,0.02248264,0.06917138,
0.07207685,0.02974831,0.02858248]
sorted(importance)大小排序(按索引从大到小): [3, 7, 2, 18, 9, 17, 4, 12, 5, 13, 11, 19, 20, 14, 15, 10, 16, 6, 0, 8, 1]ok，大功告成，对照前面argsort()的结果与原始数组，程序运行没问题了~
总结
快速排序＋返回索引大概就这么多，至于为什么要有基于列表索引和基于指针索引两种，是因为基于列表排序的话，虽然代码简单，但每次迭代都会产生两个新的列表，数据量小还好，数据量大的话，会占用很多的内存去存储，因此从系统开销时间开销上考虑，针对单个列表使用指针效率会更高一些.其次，针对一些升序或降序的数组，以第一个元素为pivot值往往效果不佳，这时可以考虑样本中值，或者首尾平均数等作为pivot值，效果会有所提升。每次写博客都能顺便p图玩，还是很有趣的，以后会有更多的图解算法和机器学习O.O
