R语言中的排序算法

客官°小女子只卖身不卖艺 2021-09-14 11:04 537阅读 0赞

在写本篇博客之前，我曾经写过一篇名为[《程序员没有理由不知道的8大排序》][8]，在那篇博客当中，8大排序算法有详细的介绍，代码实现主要是由Java代码实现的，最近用R语言比较多，所以这次再一次整理一下R语言中的排序算法，希望对大家有所帮助，如果对排序算法的原理不清楚的话可以点击上面的链接查看我之前文章的内容，本篇文章主要以代码实现为主，原理不在此赘述了。文中如有不正确的地方，欢迎大家批评指正。

# 1.测试数据 #

# 测试数组 vector = c(5,34,65,36,67,3,6,43,69,59,25,785,10,11,14) vector ## [1] 5 34 65 36 67 3 6 43 69 59 25 785 10 11 14

# 2.R语言中自带的排序函数 #

在R中，跟排序有关的函数主要有三个：sort()，rank()，order()。其中sort(x)是对向量x进行排序，rank()是求秩的函数，它的返回值是这个向量中对应元素的“排名”，order()的返回值是对应“排名”的元素所在向量中的位置。

sort(vector)
    ##  [1]   3   5   6  10  11  14  25  34  36  43  59  65  67  69 785
    order(vector)
    ##  [1]  6  1  7 13 14 15 11  2  4  8 10  3  5  9 12
    rank(vector)
    ##  [1]  2  8 12  9 13  1  3 10 14 11  7 15  4  5  6

# 3.冒泡排序 #

# bubble sort
    bubbleSort = function(vector) {
      n = length(vector)
      for (i in 1:(n-1)) {
        for (j in (i+1):n) {
          if(vector[i]>=vector[j]){
            temp = vector[i]
            vector[i] = vector[j]
            vector[j] = temp
            }
          }
        }
      return(vector)
    }
    bubbleSort(vector)
    
    ##  [1]   3   5   6  10  11  14  25  34  36  43  59  65  67  69 785

# 4.快速排序 #

# quick sort
    quickSort = function(vector, small, big) {
      left = small
      right = big
      if (left >= right) {
        return(vector)
      }else{
        markValue = vector[left]
        while (left < right) {
          while (left < right && vector[right] >= markValue) {
            right = right - 1
          }
          vector[left] = vector[right]
          while (left < right && vector[left] <= markValue) {
            left = left + 1
          }
          vector[right] = vector[left]
        }
      vector[left] = markValue
      vector = quickSort(vector, small, left - 1)
      vector = quickSort(vector, right + 1, big)
      return(vector)
      }
    }
    quickSort(vector,1,15)
    
    ##  [1]   3   5   6  10  11  14  25  34  36  43  59  65  67  69 785

# 5.插入排序 #

# insert sort
    insertSort = function(vector){
      n = length(vector)
      for(i in 2:n){
        markValue = vector[i]
        j=i-1
        while(j>0){
          if(vector[j]>markValue){
            vector[j+1] = vector[j]
            vector[j] = markValue
          }
          j=j-1
        }
      }
      return(vector)
    }
    insertSort(vector)
    
    ##  [1]   3   5   6  10  11  14  25  34  36  43  59  65  67  69 785

# 6.希尔排序 #

# shell sort
    shellSort = function(vector){
       n = length(vector)
       separate = floor(n/2)
       while(separate>0){
         for(i in 1:separate){
           j = i+separate
           while(j<=n){
             m= j- separate
             markVlaue = vector[j]
             while(m>0){
               if(vector[m]>markVlaue){
                 vector[m+separate] = vector[m]
                 vector[m] = markVlaue
               }
               m = m-separate
             }
             j = j+separate
           }
         }
         separate = floor(separate/2)
       }
       return(vector)
    }
    shellSort(vector)
    
    ##  [1]   3   5   6  10  11  14  25  34  36  43  59  65  67  69 785

# 7.选择排序 #

# select sort
    selectSort = function(vector){
      n = length(vector)
      for(i in 1:(n-1)){
        minIndex = i
        for(j in (i+1):n){
          if(vector[minIndex]>vector[j]){
            minIndex = j
          }
        }
        temp = vector[i]
        vector[i] = vector[minIndex]
        vector[minIndex] = temp
      }
      return(vector)
    }
    selectSort(vector)
    
    ##  [1]   3   5   6  10  11  14  25  34  36  43  59  65  67  69 785

# 8.堆排序 #

# heap sort
    adjustHeap = function(vector,k,n){
      left = 2*k
      right = 2*k+1
      max = k
      if(k<=n/2){
        if(left<=n&&vector[left]>=vector[max]){
          max = left
        }
        if(right<=n&&vector[right]>=vector[max]){
          max = right
        }
        if(max!=k){
          temp = vector[k]
          vector[k] = vector[max]
          vector[max] = temp
          vector = adjustHeap(vector,max,n)
        }
      }
      return(vector)
    }
    createHeap = function(vector,n){
      for(i in (n/2):1){
        vector = adjustHeap(vector,i,n)
      }
      return(vector)
    }
    heapSort = function(vector){
      n = length(vector)
      vector = createHeap(vector,n)
      for(i in 1:n){
        temp = vector[n-i+1]
        vector[n-i+1] = vector[1]
        vector[1] = temp
        vector = adjustHeap(vector,1,n-i)
      }
      return(vector)
    }

# 9.归并排序 #

# merge sort
    combine = function(leftSet,rightSet){
      m = 1
      n = 1
      vectorTemp = c()
      while (m<=length(leftSet)&&n<=length(rightSet)) {
        if(leftSet[m]<=rightSet[n]){
          vectorTemp = append(vectorTemp,leftSet[m])
          m = m+1
        }else{
          vectorTemp = append(vectorTemp,rightSet[n])
          n = n+1
        }
      }
      if(m>length(leftSet)&&n==length(rightSet)){
        vectorTemp = append(vectorTemp,rightSet[n:length(rightSet)])
      }else if(m==length(leftSet)&&n>length(rightSet)){
        vectorTemp = append(vectorTemp,leftSet[m:length(leftSet)])
      }
      return(vectorTemp)
    }
    mergeSort = function(vector){
      size = length(vector)
      if(size==1){
        return(vector)
      }
        cut = ceiling(size/2)
        leftSet = mergeSort(vector[1:cut])
        rightSet = mergeSort(vector[(cut+1):size])
        vector = combine(leftSet,rightSet)
        return(vector)
    }

[8]: http://blog.csdn.net/gdkyxy2013/article/details/76768815