排序算法(二).Rmd

---
title: "排序算法(二)"
author: "linsq"
date: "2017年4月12日"
output: html_document
---

```{r setup, include=FALSE}
knitr::opts_chunk$set(echo = TRUE)
```



##冒泡排序

冒泡排序是一种流行但是低效的排序算法，它的作用时反复交换相邻的未按次序排列的元素。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

算法：          
BUBBLESORT(A):          
  for i=1 and A.length-1
        for j=A.length downto i+1               
                ifA[j]<A[j-1]           
                        exchangeA[j] with A[j-1]

R代码：
```{r}
bubblesort <- function(x){
        n <- length(x)
        for(i in 1:(n-1)){
                for(j in (i+1):n){
z                        if(x[i]>=x[j]){
                                m <- x[j]
                                x[j]=x[i]
                                x[i]=m
                        }
                }
        }
        return(x)
}

bubblesort(a)
```

冒泡排序时间复杂度最好为O(n),最差为O(n^2),平均情况为O(n^2),空间复杂度为O(1)，结果稳定。



##快速排序

快速排序是冒泡算法的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据要小，然后再按此方法对这两部分数据进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。                
其中每一次递归为：              
对挖坑填数进行总结
1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。
2．j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。           


```{r}
fastsort <- function(x,small,big){
        left <- small
        right <- big
        if(left>=right){
                return(x)
        }else{
                key <- x[left]
                while(left<right){
                        while(left<right & x[right]>=key){
                                right <- right-1
                        }
                        x[left] <- x[right]
                        while(left<right & x[left]<=key){
                                left <- left+1
                        }
                        x[right] <- x[left]
                }
                x[left] <- key
                x <- fastsort(x,small,left-1)
                x <- fastsort(x,right+1,big)
                return(x)
        }
}

a <- c(31,41,59,26,41,58)
fastsort(a,1,length(a))

```

快速排序的时间复杂度在最好情况下为O(n)，最差情况为O(n^2),平均情况为O(nlog_2(n))，时间复杂度为O(1)，这是不稳定的排序方法。