算法之简单排序-白红宇

一。直接插入排序

1。直接插入排序：

直接插入排序是一种简单的排序方法，它的基本思想是将待排序的记录按照其值的大小插入到已排好序的有序表的适当位置，直到全部插入完为止。举个整型的排序例子

2。直接插入排序的伪代码：

insertionsort(data[])

for

to data.length

tmp

data[i];

将所有大于tmp的元素data[j]向后移动一位;

将tmp放在正确的位置上;

3.简单例子，以整型为例。

A）ruby语言实现：

def insertion_sort(a)

while

length

tmp

a[i]

while

break

tmp

a[j

]

a[j]

a[j

]

end

a[j]

tmp

end

[

]

insertion_sort(a)

each

{

to_s

}

B）java语言实现：

package

com.sohu.blog.denns_zane.sort;

public

class

InsertSort

{

public

static

void

main(String args[])

{

int

[]data

{

}

;

insertsort(data);

for

(

int

data.length;i

)

{

System.out.print(data[i]

);

}

public

static

void

insertsort(

int

[]data)

{

for

(

int

,j;i

data.length;i

)

{

int

tmp

data[i];

for

i;j

tmp

data[j

];j

)

data[j]

data[j

];

data[j]

tmp;

}

5。算法复杂度：

最好情况：进行n-1次比较和2(n-1)次移动，尽管他们其实都是多余的，复杂度O(n)

最坏情况：具体计算略，O(n*n)

平均情况：O(n*n)，也就是接近最坏情况，在平均情况下，数组大小翻倍，它的排序工作将是原来的4倍。

二。选择排序

1。算法描述：选择算法试图先查找一个放错位置的元素并将它放到最终位置上，以此来局部化数组元素的交换。选择值最小的元素并将它和第一个位置上的元素交换。在第i步中，查找data[i],...,data[n-1]中的最小元素，并将它和data[i]进行交换。重复此过程，直到所有的元素都放入正确的位置为止。

2。伪代码描述：

selectionsort(data[])

for

to data.length

从data[i],

,data[n

]中选取最小的元素

将它和data[i]交换

3。实现，以整型数组为例：

1)ruby语言实现：

def selection_sort(a)

least

for

i in (

length

))

least

while

length

a[j]

a[least]

least

end

a[least]

a[i]

a[least]

unless

least

交换

end

[

]

selection_sort(a)

each

{

to_s

}

代码很好理解，不做解释。

2）java语言实现：

package

com

sohu

blog

denns_zane

sort

;

public class SelectionSort{

public static

int

[] selection_sort(

int

[] data){

int

least

;

for

data

length

){

for

least

i;j

data

length

)

(data[j]

data[least])

least

(least

swap(data

least

i);

½»»»data[i]ºÍ×îÐ¡ÔªËØ

}

return

data;

}

public static void swap(

int

[]data

int

least

int

i){

int

tmp

data[least];

data[least]

data[i];

data[i]

tmp;

}

public static void main(String args[]){

int

[] t

{

};

selection_sort(t);

for

(

int

t){

System

out

);

}

4.算法效率：

任何情况下，都需要进行n*(n-1)/2次比较，也就是O(n*n)的复杂度

最好情况：数组已经排序，不需要交换任何元素

最坏情况：最大元素在第一个位置而其他元素有序时，需要进行3*(n-1)次交换，即O(n)，也是很好的结果

三。冒泡排序

1。算法伪代码描述：

bubblesort(data[])

for

to data.length

for

data.length

downto i

如果顺序错误，就交换j和j

1位置上的元素

2。实现：

1)ruby语言实现：

def bubble_sort(data)

for

i in (

(data

length

))

data

length

while

data[j]

data[j

]

data[j]

data[j

]

data[j

]

data[j]

交换

end

[

]

bubble_sort(a)

each

{

to_s

}

2）java语言实现：

package

com.sohu.blog.denns_zane.sort;

public

class

BubbleSort

{

public

static

void

bubble_sort(

int

[] data)

{

for

(

int

data.length

)

for

(

int

data.length

i;j

)

(data[j]

data[j

])

swap(data,j,j

);

}

public

static

void

swap(

int

[]data,

int

least,

int

{

int

tmp

data[least];

data[least]

data[i];

data[i]

tmp;

}

public

static

void

main(String args[])

{

int

[] t

{

}

;

bubble_sort(t);

for

(

int

i:t)

{

System.out.print(i

);

}

3。算法效率：

冒泡排序的比较次数近似是插入排序的两倍，和选择排序相同；移动次数和插入排序相同，是选择排序的n倍。可以说，插入排序比冒泡排序快两倍。

文章转自庄周梦蝶，原文发布时间5.17