而第二有的就只包涵这个因素(即待插入元素)

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

正文用Python达成了插入排序、希尔排序、冒泡排序、飞快排序、直接采用排序、堆排序、归并排序、基数排序。

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

1、插入排序

描述
插入排序的基本操作就是将一个数额插入到已经排好序的逐步数据中,从而赢得一个新的、个数加一的平稳数据,算法适用于少量数量的排序,时间复杂度为O(n^2)。是安静的排序方法。插入算法把要排序的数组分成两有些:第一有的含有了那些数组的有着因素,但将最终一个要素除外(让数组多一个上空才有插入的职位),而第二部分就只含有那一个要素(即待插入元素)。在第一有的排序已毕后,再将以此最后元素插入到已排好序的首先片段中。
代码完毕

def insert_sort(lists):
    # 插入排序
    count = len(lists)
    for i in range(1, count):
        key = lists[i]
        j = i - 1
        while j >= 0:
            if lists[j] > key:
                lists[j + 1] = lists[j]
                lists[j] = key
            j -= 1
    return lists

 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

2、希尔排序

描述
希尔排序(Shell
Sort)是插入排序的一种。也称减弱增量排序,是直接插入排序算法的一种更敏捷的革新版本。希尔排序是非稳定排序算法。该办法因DL.Shell于1959年提出而得名。
希尔排序是把记录按下标的终将增量分组,对每组使用直接插入排序算法排序;随着增量渐渐滑坡,每组包罗的显要词越来越多,当增量减至1时,整个文件恰被分成一组,算法便停下。
代码达成

def shell_sort(lists):
    # 希尔排序
    count = len(lists)
    step = 2
    group = count / step
    while group > 0:
        for i in range(0, group):
            j = i + group
            while j < count:
                k = j - group
                key = lists[j]
                while k >= 0:
                    if lists[k] > key:
                        lists[k + group] = lists[k]
                        lists[k] = key
                    k -= group
                j += group
        group /= step
    return lists

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

3、冒泡排序

描述
它再度地访问过要排序的数列,四回比较多少个要素,若是他们的相继错误就把她们交流过来。走访数列的工作是再一次地开展直到没有再须求互换,也就是说该数列已经排序已毕。
代码达成

def bubble_sort(lists):
    # 冒泡排序
    count = len(lists)
    for i in range(0, count):
        for j in range(i + 1, count):
            if lists[i] > lists[j]:
                lists[i], lists[j] = lists[j], lists[i]
    return lists

5 插入排序

有一个早已平稳的数码系列,须求在那几个曾经排好的数额体系中插入一个数,但必要插入后此数据种类依旧雷打不动,那么些时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数码插入到已经排好序的雷打不动数据中,从而获得一个新的、个数加一的逐步数据,算法适用于少量多少的排序,时间复杂度为O(n^2)。是安静的排序方法。插入算法把要排序的数组分成两部分:第一部分含有了这些数组的所有因素,但将最终一个元素除外(让数组多一个空中才有插入的职分),而第二局地就只包涵这个要素(即待插入元素)。在第一片段排序完结后,再将那些最后元素插入到已排好序的率先有些中。插入排序的中坚思想是:每步将一个待排序的纪要,按其根本码值的大小插入后面早已排序的文书中正好地方上,直到所有布置完截至。

# 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

4、快速排序

描述
通过一趟排序将要排序的多少分割成独立的两有些,其中有些的装有数据都比别的一些的兼具数据都要小,然后再按此方法对那两局地数据分别开展高效排序,整个排序进程可以递归举办,以此达到总体数据变成有序连串。
代码完成

def quick_sort(lists, left, right):
    # 快速排序
    if left >= right:
        return lists
    key = lists[left]
    low = left
    high = right
    while left < right:
        while left < right and lists[right] >= key:
            right -= 1
        lists[left] = lists[right]
        while left < right and lists[left] <= key:
            left += 1
        lists[right] = lists[left]
    lists[right] = key
    quick_sort(lists, low, left - 1)
    quick_sort(lists, left + 1, high)
    return lists

6.希尔排序

希尔排序是插入排序的一种,也称收缩增量排序,是直接插入排序算法的一种更高速的革新版本。希尔排序是非稳定排序算法。希尔排序是把记录按下标的肯定增量分组,对每组使用直接插入排序算法排序;随着增量渐渐减小,每组包涵的根本词越多,当增量减至1时,整个文件恰被分成一组,算法便偃旗息鼓。

# 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

5、直接采纳排序

描述
主旨境维:第1趟,在待排序记录r1 ~
r[n]中选出最小的笔录,将它与r1交流;第2趟,在待排序记录r2 ~
r[n]中选出最小的笔录,将它与r2调换;以此类推,第i趟在待排序记录r[i]
~
r[n]中选出最小的记录,将它与r[i]交流,使有序体系不断增强直到一切排序完成。
代码完毕

def select_sort(lists):
    # 选择排序
    count = len(lists)
    for i in range(0, count):
        min = i
        for j in range(i + 1, count):
            if lists[min] > lists[j]:
                min = j
        lists[min], lists[i] = lists[i], lists[min]
    return lists

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

6、堆排序

描述
堆排序(Heapsort)是指利用堆积树(堆)那种数据结构所设计的一种排序算法,它是挑选排序的一种。可以行使数组的特点急速稳定指定索引的要素。堆分为大根堆和小根堆,是截然二叉树。大根堆的渴求是每个节点的值都不超过其父节点的值,即A[PARENT[i]]
>=
A[i]。在数组的非降序排序中,要求采纳的就是大根堆,因为根据大根堆的必要可以,最大的值一定在堆顶。
代码完成

def adjust_heap(lists, i, size):
    lchild = 2 * i + 1
    rchild = 2 * i + 2
    max = i
    if i < size / 2:
        if lchild < size and lists[lchild] > lists[max]:
            max = lchild
        if rchild < size and lists[rchild] > lists[max]:
            max = rchild
        if max != i:
            lists[max], lists[i] = lists[i], lists[max]
            adjust_heap(lists, max, size)

def build_heap(lists, size):
    for i in range(0, (size/2))[::-1]:
        adjust_heap(lists, i, size)

def heap_sort(lists):
    size = len(lists)
    build_heap(lists, size)
    for i in range(0, size)[::-1]:
        lists[0], lists[i] = lists[i], lists[0]
        adjust_heap(lists, 0, i)

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)
}

7、归并排序

描述
归并排序是创建在集合操作上的一种有效的排序算法,该算法是应用分治法(Divide
and
Conquer)的一个格外出众的利用。将已有序的子连串合并,得到完全有序的连串;即先使每个子体系有序,再使子序列段间有序。若将多个静止表合并成一个静止表,称为二路归并。
归并经过为:相比较a[i]和a[j]的大小,若a[i]≤a[j],则将率先个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1;否则将第四个有序表中的元素a[j]复制到r[k]中,并令j和k分别加上1,如此循环往复下去,直到其中一个逐步表取完,然后再将另一个平稳表中多余的因素复制到r中从下标k到下标t的单元。归并排序的算法大家平日用递归完成,先把待排序区间[s,t]以中点二分,接着把左侧子区间排序,再把左侧子区间排序,最后把左区间和右区间用一次归并操作合并成有序的间距[s,t]。
代码完成

def merge(left, right):
    i, j = 0, 0
    result = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result

def merge_sort(lists):
    # 归并排序
    if len(lists) <= 1:
        return lists
    num = len(lists) / 2
    left = merge_sort(lists[:num])
    right = merge_sort(lists[num:])
    return merge(left, right)

9.归并排序

归并排序是起家在集合操作上的一种有效的排序算法,该算法是拔取分治法的一个非常优异的应用。将已有序的子体系合并,获得完全有序的种类;即先使种种子种类有序,再使子系列段间有序。若将四个静止表合并成一个逐步表,称为二路归并。归并经过为:相比较a[i]和a[j]的大小,若a[i]≤a[j],则将第三个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1;否则将第四个有序表中的元素a[j]复制到r[k]中,并令j和k分别加上1,如此循环下去,直到其中一个逐步表取完,然后再将另一个平稳表中多余的因素复制到r中从下标k到下标t的单元。归并排序的算法大家日常用递归完成,先把待排序区间[s,t]以中点二分,接着把右边子区间排序,再把右侧子区间排序,最终把左区间和右区间用三遍归并操作合并成有序的间距[s,t]。

# 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)
}

 

本文链接:http://www.cnblogs.com/homewch/p/5927280.html

8、基数排序

描述
基数排序(radix sort)属于“分配式排序”(distribution
sort),又称“桶子法”(bucket sort)或bin
sort,顾名思义,它是透过键值的部份资讯,将要排序的要素分配至某些“桶”中,藉以达到排序的效果,基数排序法是属于稳定性的排序,其时间复杂度为O
(nlog(r)m),其中r为所使用的基数,而m为堆数,在好哪天候,基数排序法的功能当先其他的安定排序法。
代码完毕

import math
def radix_sort(lists, radix=10):
    k = int(math.ceil(math.log(max(lists), radix)))
    bucket = [[] for i in range(radix)]
    for i in range(1, k+1):
        for j in lists:
            bucket[j/(radix**(i-1)) % (radix**i)].append(j)
        del lists[:]
        for z in bucket:
            lists += z
            del z[:]
    return lists

来源:
http://python.jobbole.com/82270/

相关文章