冒泡排序、選擇排序、插入排序以及二分法查找算法

2019-11-06 06:25:47

字體：大中小

來源：轉載

供稿：網友

冒泡排序 冒泡排序（Bubble Sort，臺灣譯為：泡沫排序或氣泡排序）是一種簡單的排序算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。 選擇排序 選擇排序(Selection sort)是一種簡單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小元素，然后放到排序序列末尾。以此類推，直到所有元素均排序完畢。 插入排序 插入排序（Insertion Sort）的算法描述是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。插入排序在實現上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。 二分法查找算法 二分查找又稱折半查找，優點是比較次數少，查找速度快，平均性能好；其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經常變動而查找頻繁的有序列表。

java代碼

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.php代碼<?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;}//選擇排序法1function 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;}//選擇排序法2function 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);?>

其他不怎么經常見到的算法，改天再研究！我的博客：http://blog.greeGhost.com

上一篇：POJ1860 SPFA判斷正環

下一篇：BZOJ2802: [Poi2012]Warehouse Store