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

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.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代码

<?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