采用索引的方法来实现几种经典的排序算法

        排序算法相信很多人都比较了解，比如插入排序，选择排序，快速排序，归并排序，堆排序等等。不过有的时候我们需要排序的元素可能所占的字节比较大，直接排序肯定避免不了元素的交换操作，这样其实对内存来说消耗是比较大的，而且时间效率上也会有所下降，这个时候可以考虑增加一个索引数组index[ ]的策略来进行排序，见下图：

 我们只需要对索引数组来进行排序，而不改变原数组中的元素的位置，这就避免了直接交换数组元素的操作，下面附上几种排序的代码：

#include 
#include 
#include 
using namespace std;
//这是快速排序：
void __quick_sort(int arr[],int l,int r,int index[])
{
    if(l>=r)
	    return;
    swap(arr[index[l]],arr[index[rand()%(r-l+1)+l]]);
    int v=arr[index[l]];
    int v2=index[l];
    int l1=l,r1=r;
    while(l1=v&&l1 
//这是归并排序：
void __merge(int arr[],int l,int mid,int r,int index[])
{
     int aux[r-l+1];
     for(int i=l;i<=r;i++){
          aux[i-l]=index[i];
     }
     int i=l,j=mid+1,k=l;
     for(;k<=r;k++){
	  if(i>mid){
                index[k]=aux[j-l];
		j++;
	  }else if(j>r){
                index[k]=aux[i-l];
		i++;
	  }else if(arr[aux[i-l]]=r)
	     return;
     int mid=l+(r-l)/2;
     __mergeSort(arr,l,mid,index);
     __mergeSort(arr,mid+1,r,index);
     __merge(arr,l,mid,r,index);
}

void mergeSort(int arr[],int n,int index[])
{
     __mergeSort(arr,0,n-1,index);
}
 
//这是插入排序：
void insertSort(int arr[],int n,int index[])
{
    for(int i=1;i0&&arr[index[j-1]]>v;j--){
              index[j]=index[j-1];
	 }
	 index[j]=v2;
    }
}
 
测试结果：
 
void print(int arr[],int n)
{
    for(int i=0;i 
int main(void)
{
    srand(time(0));
    int arr[100];
    int index[100];
    int index2[100];
    int index3[100];
    int n=100;
    for(int i=0;i<100;i++){
          index[i]=i;
    }
    creat_arr(arr,100);
    copy_arr(index,n,index2);
    copy_arr(index,n,index3);
    //cout<<"打印Index2:"< 
 
       简单实现了几种采用索引方式的排序算法，其实就是将原本的算法中元素的直接交换想办法换为index[ ]这个数组中对应位置索引的交换。