Tenken blog

冒泡排序、选择排序、插入排序以及二分法查找算法

发表于 | 分类于 |

冒泡排序
冒泡排序（Bubble Sort，台湾译为：泡沫排序或气泡排序）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
选择排序
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。
插入排序
插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
二分法查找算法
二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
package demo;

public class helloworld {

	public static void main(String[] args) {
		//int a[] = {10,20,4,30,11,80,100,22};
		int a[] = {1,3,4,5,6,7,8,19,20,100,222,230};
		//bubbleSort(a);
		binarySearch(a,5);
		//selectSort(a);
		//insertSort(a);
		
	}
	//冒泡排序
	public static void bubbleSort(int a[]){
		int temp = 0;
		for(int i=1;i<a.length;i++){
			for(int j=0;j<a.length-1;j++){
				if(a[j]<a[j+1]){
					temp = a[j];
					a[j] = a[j+1];
					a[j+1] = temp;
				}
			}
		}
		System.out.println("");
		System.out.println("冒泡排序:");
		for(int x : a){
			System.out.print(x+" ");
		}
	}
	//选择排序
	public static void selectSort(int a[]){
		int x=0,y=0;
		for(int i=0;i<a.length-1;i++){
			x=i;y=a[i];
			for(int j=i+1;j<a.length;j++){
				if(y<a[j]){
					y=a[j];
					x=j;
				}
			}
			if(y!=a[i]){
				a[x] = a[i];
				a[i] = y;
			}
			
		}
		System.out.println("");
		System.out.println("选择排序:");
		for(int k : a){
			System.out.print(k+" ");
		}
		
	}
	//选择排序1
	public static void selectSort1(int a[]){
		int temp;
		for(int i=0;i<a.length-1;i++){
			for(int j=i+1;j<a.length;j++){
				if(a[i]<a[j]){
					temp = a[i];
					a[i] = a[j];
					a[j] = temp;
				}
			}	
		}
		System.out.println("");
		System.out.println("选择排序1:");
		for(int k : a){
			System.out.print(k+" ");
		}
		
	}
	//插入排序
	public static void insertSort(int a[]){
		int x=0,y=0;
		for(int i=1;i<a.length;i++){
			if(a[i] > a[i-1]){
				x=a[i];
				y = i-1;
				while(y>=0 && x>a[y]){
					a[y+1] = a[y];
					y--;
				}
				
				a[y+1] = x;
				
			}
			
		}
		System.out.println("");
		System.out.println("插入排序:");
		for(int k : a){
			System.out.print(k+" ");
		}
		
	}
	//二分法查找（递归）
	public static void binarySearch(int a[],int left,int right,int find){
		if(right>=left){
			int mid = (right+left)/2;
			if(find == a[mid]){
				System.out.print("找到了,第"+(mid+1)+"位");
			}else if(find > a[mid]){
				binarySearch(a,mid+1,right,find);
			}else if(find < a[mid]){
				binarySearch(a,left,mid-1,find);
			}
		}else{
			System.out.print("没找到");
		}
		
		
	}
	//二分法查找（循环）
	public static void binarySearch(int a[], int find){
		int mid = a.length/2;
		if(a[mid] == find){
			System.out.print("找到了,第"+(mid+1)+"位");
			return;
		}
		int left = 0;
		int right = a.length-1;
		while(left <= right){
			mid = (left+right)/2;
			if(a[mid] == find){
				System.out.print("找到了,第"+(mid+1)+"位");
				return;
			}else if(find < a[mid]){
				right = mid-1;
			}else if(find > a[mid]){
				left = mid+1;
			}
		}
		System.out.print("没找到");
	}
}

PHP代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
<?php
//冒泡排序法
function bubbleSort($arr){
	if(!is_array($arr)) return;
	$temp=0;
	for($i=1;$i<count($arr);$i++){
		for($j=0;$j<count($arr)-1;$j++){
			if($arr[$j]<$arr[$j+1]){
				$temp = $arr[$j+1];
				$arr[$j+1] = $arr[$j];
				$arr[$j] = $temp;
			}
		}
	}
	return $arr;
}

//选择排序法1
function selectSort($arr){
	if(!is_array($arr)) return;
	for($i=0;$i<count($arr)-1;$i++){
		$x=$arr[$i];$y=$i;
		for($j=$i+1;$j<count($arr);$j++){
			if($x < $arr[$j]){
				$x=$arr[$j];
				$y=$j;
			}
		}
		if($x != $arr[$i]){
			$arr[$y] = $arr[$i];
			$arr[$i] = $x;
		}
	}
	return $arr;
}
//选择排序法2
function selectSort1($arr){
	if(!is_array($arr)) return;
	$temp=0;
	for($i=0;$i<count($arr)-1;$i++){
		for($j=$i+1;$j<count($arr);$j++){
			if($arr[$i] < $arr[$j]){
				$temp = $arr[$j];
				$arr[$j] = $arr[$i];
				$arr[$i] = $temp;
			}
		}
	}
	return $arr;
}

//插入排序法
function insertSort($arr){
	if(!is_array($arr)) return;
	for($i=1;$i<count($arr);$i++){
		if($arr[$i] > $arr[$i-1]){
			$x = $arr[$i];
			$y = $i-1;
			while($y >= 0 && $x>$arr[$y]){
				$arr[$y+1] = $arr[$y];
				$y--;
			}
			$arr[$y+1] = $x;
		}
	}
	return $arr;
}

//二分法查找(递归算法)
function binarySearch($arr, $left, $right, $find){
	if(!is_array($arr)) return;
	if($right >= $left){
		$mid = floor(($left+$right)/2);
		if($arr[$mid] == $find){
			return $mid;
		}

		if($arr[$mid] > $find){
			return binarySearch($arr, $left, $mid-1, $find);
		}

		if($arr[$mid] < $find){
			return binarySearch($arr, $mid+1, $right, $find);
		}
	}
	
}

//二分法查找（循环算法）
function binarySearch1($arr, $find){
	if(!is_array($arr)) return;
	$mid = floor(count($arr)/2);
	if($arr[$mid] == $find){
		return $mid;
	}
	$left = 0;
	$right = count($arr)-1;
	while($left <= $right){
		$mid = floor(($left+$right)/2);
		if($arr[$mid] == $find){
			return $mid;
		}elseif($arr[$mid] > $find){
			$right = $mid-1;
		}elseif($arr[$mid] < $find){
			$left = $mid+1;
		}
	}
}
//$arr = array(2,10,333,11,1,22,100,20);
//$arr = bubbleSort($arr);
$arr = array(1,2,3,4,5,6,7,8,9,10);
$arr = binarySearch1($arr,7);
echo "<pre>";
print_r($arr);
?>

其他不怎么经常见到的算法，改天再研究！

请我吃辣条吧~~