摘要：需求：分別用 冒泡排序法，選擇排序法，插入排序法，快速排序法將下面數組中 的值按照從小到的順序進行排序。?$arr = array(1,33,3,345,5,63,7,822,9,512);1.冒泡排序...

需求：分別用 冒泡排序法，選擇排序法，插入排序法，快速排序法將下面數組中 的值按照從小到的順序進行排序。

$arr = array(1,33,3,345,5,63,7,822,9,512);

1. 冒泡排序

思路分析：在要排序的一組數中，對當前還未排好的序列，從前往后對相鄰的兩個數依次進行比較和調整，讓較大的數往下沉，較小的往上冒。即，每當兩相鄰的數比較后發現它們的排序與排序要求相反時，就將它們互換。

function bubble_sort($arr){
	$len = count($arr);
	//該層循環控制 需要冒泡的輪數
	for($i=1; $i<$len; $i++){ 
		//該層循環用來控制每輪 冒出一個數 需要比較的次數
		for($k=0; $k<$len-$i; $k++){
			if($arr[$k] > $arr[$k+1]){
				$tmp = $arr[$k+1];
				$arr[$k+1] = $arr[$k];
				$arr[$k] = $tmp;
			}
		}
	}
	return $arr;
}

2. 選擇排序

思路分析：在要排序的一組數中，選出最小的一個數與第一個位置的數交換。然后在剩下的數當中再找最小的與第二個位置的數交換，如此循環到倒數第二個數和最后一個數比較為止。

function select_sort($arr){
    $len = count($arr);
    for($i=0; $i<$len-1; $i++) {
        $p = $i;
        for($j=$i+1; $j<$len; $j++) {
            if($arr[$p] > $arr[$j]) {
                $p = $j;
            }
        }
        if($p != $i) {
            $tmp = $arr[$p];
            $arr[$p] = $arr[$i];
            $arr[$i] = $tmp;
        }
    }
    return $arr;
}

3.插入排序

思路分析：在要排序的一組數中，假設前面的數已經是排好順序的，現在要把第n個數插到前面的有序數中，使得這n個數也是排好順序的。如此反復循環，直到全部排好順序。

function insert_sort($arr){
    $len = count($arr); 
    for($i=1; $i<$len; $i++) {
        $tmp = $arr[$i];
        for($j=$i-1;$j>=0;$j--) {
            if($tmp < $arr[$j]) {
                //發現插入的元素要小，交換位置，將后邊的元素與前面的元素互換
                $arr[$j+1] = $arr[$j];
                $arr[$j] = $tmp;
            } else {
                //如果碰到不需要移動的元素，由于是已經排序好是數組，則前面的就不需要再次比較了。
                break;
            }
        }
    }
    return $arr;
}

4.快速排序

思路分析：選擇一個基準元素，通常選擇第一個元素或者最后一個元素。通過一趟掃描，將待排序列分成兩部分，一部分比基準元素小，一部分大于等于基準元素。此時基準元素在其排好序后的正確位置，然后再用同樣的方法遞歸地排序劃分的兩部分。

function quick_sort($arr){
	//判斷參數是否是一個數組
	if(!is_array($arr)) return false;
	
	//遞歸出口:數組長度為1，直接返回數組
	$length = count($arr);
	if($length<=1) return $arr;
	
	//數組元素有多個,則定義兩個空數組
	$left = $right = array();
	
	//使用for循環進行遍歷，把第一個元素當做比較的對象
	for($i=1; $i<$length; $i++){
		//判斷當前元素的大小
		if($arr[$i] < $arr[0]){
			$left[] = $arr[$i];
		}else{
			$right[] = $arr[$i];
		}
	}
	//遞歸調用
	$left = quick_sort($left);
	$right = quick_sort($right);
	
	//將所有的結果合并
	return array_merge($left,array($arr[0]),$right);
}