给定0~N之间的N个数字(大于等于0,小于N,不重复)进行按小到大排列(不用其它的经典排序算法)

1 问题

比如我们给定0~N之间的N个数字(大于等于0,小于N,并且不重复)进行按小到大排列,比如N是5,我们给定数据{3, 2, 1, 0, 4},我们按照从小到大的排名最后就是{0, 1, 2, 3, 4}

2 思路

我们遍历数组,下标为i,我们把i和a[i]进行对比,如果不想等我们就进行交换a[i]和a[a[i]]的值,我们知道题目要求是0~N,所以a[a[i]]不会下标越界.如果发现i和a[i]相等,我们再把++i

3 代码实现

  

   

    

     

    
    

     
  1 #include <iostream>
     
    
   

    

     

    
    

     
  2 #include <stdlib.h>
     
    
   

    

     

    
    

     
  3 using namespace std;
     
    
   

    

     

    
    

     
  4 
     
    
   

    

     

    
    

     
  5 
     
    
   

    

     

    
    

     
  6 void permutation(int *a, int length)
     
    
   

    

     

    
    

     
  7 {
     
    
   

    

     

    
    

     
  8 if (a == NULL || length <= 0)
     
    
   

    

     

    
    

     
  9 {
     
    
   

    

     

    
    

     
 10 return;
     
    
   

    

     

    
    

     
 11 }
     
    
   

    

     

    
    

     
 12 int count = 0;
     
    
   

    

     

    
    

     
 13 for (int i = 0; i < length; ++i)
     
    
   

    

     

    
    

     
 14 {
     
    
   

    

     

    
    

     
 15 while (a[i] != i)
     
    
   

    

     

    
    

     
 16 {
     
    
   

    

     

    
    

     
 17 int temp = a[a[i]];
     
    
   

    

     

    
    

     
 18 a[a[i]] = a[i];
     
    
   

    

     

    
    

     
 19 a[i] = temp;
     
    
   

    

     

    
    

     
 20 }
     
    
   

    

     

    
    

     
 21 }
     
    
   

    

     

    
    

     
 22 }
     
    
   

    

     

    
    

     
 23 
     
    
   

    

     

    
    

     
 24 
     
    
   

    

     

    
    

     
 25 int main()
     
    
   

    

     

    
    

     
 26 {
     
    
   

    

     

    
    

     
 27 int a[6] = {3, 1, 2, 0, 5, 4};
     
    
   

    

     

    
    

     
 28 int s
     
    
  
 

文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。

原文链接：chenyu.blog.csdn.net/article/details/85144320