一、冒泡排序
冒泡排序是最基本的排序算法,它的核心思想,是进行n-1趟比较,每趟比较都把最小的元素放到前面,像吐泡泡一样,轻的元素向上冒,所以得名冒泡排序
。
过程:
实现:
PHP实现:
function bubbleSort(&$arr) {
$n = count($arr);
for($i=1; $i<$n-1; ++$i) {
for($j=$n-1; $j>=$i; --$j) {
if($arr[$j] < $arr[$j-1]) swap($arr[$j], $arr[$j-1]);
}
}
}
C++实现:
void bubbleSort(int arr[], int n) {
for(int i=1; i<n; ++i) {
for(int j=n-1; j>=i; --j) {
if(arr[j] < arr[j-1]) swap(arr[j], arr[j-1]);
}
}
}
二、插入排序
插入排序,就是不断地将一个新的元素插入到已排序好的数组中,然后比较后移元素,找到位置插入。需要进行n-1趟比较
过程:
实现:
PHP实现:
function insertSort(&$arr) {
$n = count($arr);
for($i=1; $i<$n; ++$i) {
$item = $arr[$i];
$j = $i;
while($j>0 && $item < $arr[$j-1]) {
$arr[$j] = $arr[$j-1];
--$j;
}
$arr[$j] = $item;
}
}
C++实现:
void insertSort(int arr[], int n) {
for(int i=1; i<n; ++i) {
int item = arr[i];
int j = i;
while(j>0 && item < arr[j-1]) {
arr[j] = arr[j-1];
--j;
}
arr[j] = item;
}
}
三、选择排序
选择排序就是对元素进行n-1趟处理,第i趟(i从0开始)的时候,选择出arr[i]~arr[n-1]中最小的元素,然后和arr[i]进行交换
过程:
实现:
PHP实现:
function selectSort(&$arr) {
$n = count($arr);
for($i=0; $i<$n; ++$i) {
$min = $i;
for($j=$i+1; $j<$n; ++$j) {
if($arr[$j] < $arr[$min]) $min = $j;
}
swap($arr[$i], $arr[$min]);
}
}
C++实现:
void selectSort(int arr[], int n) {
for(int i=0; i<n; ++i) {
int min = i;
for(int j=i+1; j<n; ++j) {
if(arr[j] < arr[min]) min = j;
}
swap(arr[i], arr[min]);
}
}
四、性能分析
1、冒泡排序,平均时间复杂度为O(n^2),无论输入是什么,最好最差的情况均为O(n^2),是稳定排序
2、插入排序,平均时间复杂度为O(n^2)。最好情况下,输入是已排序好的数组,所以就不需要进行比较后移的过程,时间复杂度是O(n),最差情况下,输入是逆序数组,那么比较后移的过程就要进行最大程度次,时间复杂度为O(n^2)
3、选择排序,平均时间复杂度为O(n^2),最好情况和最差情况下,均为O(n^2),不是稳定排序