常见的排序算法选择，冒泡，插入，快速，归并

　　太久没看代码了，最近打算复习一下java，又突然想到了排序算法，就把几种常见的排序算法用java敲了一遍，这里统一将无序的序列从小到大排列。选择排序
　　选择排序是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小元素，继续放在下一个位置，直到待排序元素个数为0。
　　选择排序代码如下：
　　publicvoidSelectsort（int〔〕arr）｛
　　inttemp，
　　for（inti0；i10；i）｛
　　
　　for（intji1；j10；j）｛
　　if（arr〔j〕arr〔index〕）
　　
　　｝
　　temparr〔i〕；
　　arr〔i〕arr〔index〕；
　　arr〔index〕
　　swap（arr，i，index）；
　　｝
　　System。out。print（经过选择排序后：）；
　　for（inti0；i10；i）
　　System。out。print（arr〔i〕）；
　　System。out。println（）；
　　｝冒泡排序
　　冒泡排序是一种比较基础的排序算法，其思想是相邻的元素两两比较，较大的元素放后面，较小的元素放前面，这样一次循环下来，最大元素就会归位，若数组中元素个数为n，则经过（n1）次后，所有元素就依次从小到大排好序了。整个过程如同气泡冒起，因此被称作冒泡排序。
　　选择排序代码如下：
　　publicvoidBubblesort（int〔〕arr）｛
　　
　　for（inti0；i9；i）｛
　　for（intj0；j10i1；j）｛
　　if（arr〔j〕arr〔j1〕）｛
　　temparr〔j〕；
　　arr〔j〕arr〔j1〕；
　　arr〔j1〕
　　swap（arr，j，j1）；
　　｝
　　｝
　　｝
　　System。out。print（经过冒泡排序后：）；
　　for（inti0；i10；i）
　　System。out。print（arr〔i〕）；
　　System。out。println（）；
　　｝插入排序
　　插入排序也是一种常见的排序算法，插入排序的思想是：创建一个与待排序数组等大的数组，每次取出一个待排序数组中的元素，然后将其插入到新数组中合适的位置，使新数组中的元素保持从小到大的顺序。
　　插入排序代码如下：
　　publicvoidInsertsort（int〔〕arr）｛
　　intlengtharr。
　　int〔〕arrsortnewint〔length〕；
　　intcount0；
　　for（inti0；i）｛
　　if（count0）｛
　　arrsort〔0〕arr〔0〕；
　　｝elseif（arr〔i〕arrsort〔count1〕）｛
　　arrsort〔count〕arr〔i〕；
　　｝elseif（arr〔i〕arrsort〔0〕）｛
　　insert（arr，arrsort，arr〔i〕，0，count）；
　　｝else｛
　　for（intj0；jcount1；j）｛
　　if（arr〔i〕arrsort〔j〕arr〔i〕arrsort〔j1〕）｛
　　insert（arr，arrsort，arr〔i〕，j1，count）；
　　
　　｝
　　｝
　　｝
　　
　　｝
　　System。out。print（经过插入排序后：）；
　　for（inti0；i10；i）
　　System。out。print（arrsort〔i〕）；
　　System。out。println（）；
　　｝
　　publicvoidinsert（int〔〕arr，int〔〕arrsort，intvalue，intindex，intcount）｛
　　for（i）
　　arrsort〔i〕arrsort〔i1〕；
　　arrsort〔index〕
　　｝快速排序
　　快速排序的效率比冒泡排序算法有大幅提升。因为使用冒泡排序时，一次外循环只能归位一个值，有n个元素最多就要执行（n1）次外循环。而使用快速排序时，一次可以将所有元素按大小分成两堆，也就是平均情况下需要logn轮就可以完成排序。
　　快速排序的思想是：每趟排序时选出一个基准值（这里以首元素为基准值），然后将所有元素与该基准值比较，并按大小分成左右两堆，然后递归执行该过程，直到所有元素都完成排序。
　　publicvoidQuicksort（int〔〕arr，intleft，intright）｛
　　if（leftright）
　　
　　inttemp，t；
　　
　　
　　temparr〔left〕；
　　while（ij）｛
　　while（arr〔j〕tempij）
　　j；
　　while（arr〔i〕tempij）
　　i；
　　if（ij）｛
　　tarr〔i〕；
　　arr〔i〕arr〔j〕；
　　arr〔j〕t；
　　｝
　　｝
　　arr〔left〕arr〔i〕；
　　arr〔i〕
　　Quicksort（arr，left，i1）；
　　Quicksort（arr，i1，right）；
　　｝归并排序
　　归并排序是建立在归并操作上的一种有效的排序算法，归并排序对序列的元素进行逐层折半分组，然后从最小分组开始比较排序，每两个小分组合并成一个大的分组，逐层进行，最终所有的元素都是有序的。
　　publicvoidMergesort（int〔〕arr，intleft，intright）｛
　　if（rightleft0）｛
　　int〔〕arr1newint〔（rightleft）21〕；
　　int〔〕arr2newint〔（rightleft1）2〕；
　　intj0；
　　intk0；
　　for（i）｛
　　if（i（rightleft）2）｛
　　arr1〔j〕arr〔i〕；
　　｝else｛
　　arr2〔k〕arr〔i〕；
　　｝
　　｝
　　Mergesort（arr1，0，（rightleft）2）；
　　Mergesort（arr2，0，（rightleft1）2）；
　　Merge（arr1，arr2，arr）；
　　｝
　　｝
　　publicvoidMerge（int〔〕arr1，int〔〕arr2，int〔〕arr）｛
　　inti0；
　　intj0；
　　intk0；
　　intL1arr1。
　　intL2arr2。
　　while（iL1jL2）｛
　　if（arr1〔i〕arr2〔j〕）｛
　　arr〔k〕arr1〔i〕；
　　i；
　　｝else｛
　　arr〔k〕arr2〔j〕；
　　j；
　　｝
　　k；
　　｝
　　if（iL1）｛
　　for（jL2；j）
　　arr〔k〕arr2〔j〕；
　　｝else｛
　　for（iL1；i）
　　arr〔k〕arr1〔i〕；
　　｝
　　｝
　　归并排序这里我使用了left，right等变量，使其可以通用，并没有直接用数字表示那么明确，所以给出相关伪代码，便于理解。
　　Mergesort（arr〔0。。。n1〕）
　　输入：一个可排序数组arr〔0。。。n1〕
　　输出：非降序排列的数组arr〔0。。。n1〕
　　ifn1
　　copyarr〔0。。。n21〕toarr1〔0。。。（n1）21〕确保arr1中元素个数arr2中元素个数
　　对于总个数为奇数时，arr1比arr2中元素多一个；对于总个数为偶数时，没有影响
　　copyarr〔n2。。。n1〕toarr2〔0。。。n21〕
　　Mergesort（arr1〔0。。。（n1）21〕）
　　Mergesort（arr2〔0。。。n21〕）
　　Merge（arr1，arr2，arr）
　　Merge（arr1〔0。。。p1〕，arr2〔0。。。q1〕，arr〔0。。。pq1〕）
　　输入：两个有序数组arr1〔0。。。p1〕和arr2〔0。。。q1〕
　　输出：将arr1与arr2两数组合并到arr
　　inti0；j0；k0
　　whileipandjqdo
　　ifarr1〔i〕arr2〔j〕
　　arr〔k〕arr1〔i〕
　　ii1
　　elsearr〔k〕arr2〔j〕；jj1
　　kk1
　　ifip
　　copyarr2〔j。。。q1〕toarr〔k。。。pq1〕
　　elsecopyarr1〔i。。。p1〕toarr〔k。。。pq1〕最后，完整代码如下：
　　packagetest1；
　　importjava。util。S
　　publicclassTest01｛
　　publicstaticvoidmain（String〔〕args）｛
　　ScannerscnewScanner（System。in）；
　　int〔〕arr1newint〔10〕；
　　for（inti0；i10；i）
　　arr1〔i〕sc。nextInt（）；
　　Sortdemo1newSort（）；
　　15一次只能运行一个，若多个同时运行，则只有第一个有效，后面几个是无效排序。因为第一个运行的已经将带排序数组排好序。
　　demo1。Selectsort（arr1）；1
　　demo1。Bubblesort（arr1）；2
　　3
　　demo1。Quicksort（arr1，0，arr1。length1）；
　　System。out。print（经过快速排序后：）；
　　for（inti0；i10；i）
　　System。out。print（arr1〔i〕）；
　　System。out。println（）；
　　demo1。Insertsort（arr1）；4
　　5
　　demo1。Mergesort（arr1，0，arr1。length1）；
　　System。out。print（经过归并排序后：）；
　　for（inti0；i10；i）
　　System。out。print（arr1〔i〕）；
　　System。out。println（）；
　　｝
　　｝
　　classSort｛
　　publicvoidswap（intarr〔〕，inta，intb）｛
　　
　　tarr〔a〕；
　　arr〔a〕arr〔b〕；
　　arr〔b〕t；
　　｝
　　publicvoidSelectsort（int〔〕arr）｛
　　inttemp，
　　for（inti0；i10；i）｛
　　
　　for（intji1；j10；j）｛
　　if（arr〔j〕arr〔index〕）
　　
　　｝
　　temparr〔i〕；
　　arr〔i〕arr〔index〕；
　　arr〔index〕
　　swap（arr，i，index）；
　　｝
　　System。out。print（经过选择排序后：）；
　　for（inti0；i10；i）
　　System。out。print（arr〔i〕）；
　　System。out。println（）；
　　｝
　　publicvoidBubblesort（int〔〕arr）｛
　　
　　for（inti0；i9；i）｛
　　for（intj0；j10i1；j）｛
　　if（arr〔j〕arr〔j1〕）｛
　　temparr〔j〕；
　　arr〔j〕arr〔j1〕；
　　arr〔j1〕
　　swap（arr，j，j1）；
　　｝
　　｝
　　｝
　　System。out。print（经过冒泡排序后：）；
　　for（inti0；i10；i）
　　System。out。print（arr〔i〕）；
　　System。out。println（）；
　　｝
　　publicvoidQuicksort（int〔〕arr，intleft，intright）｛
　　if（leftright）
　　
　　inttemp，t；
　　
　　
　　temparr〔left〕；
　　while（ij）｛
　　while（arr〔j〕tempij）
　　j；
　　while（arr〔i〕tempij）
　　i；
　　if（ij）｛
　　tarr〔i〕；
　　arr〔i〕arr〔j〕；
　　arr〔j〕t；
　　｝
　　｝
　　arr〔left〕arr〔i〕；
　　arr〔i〕
　　Quicksort（arr，left，i1）；
　　Quicksort（arr，i1，right）；
　　｝
　　publicvoidInsertsort（int〔〕arr）｛
　　intlengtharr。
　　int〔〕arrsortnewint〔length〕；
　　intcount0；
　　for（inti0；i）｛
　　if（count0）｛
　　arrsort〔0〕arr〔0〕；
　　｝elseif（arr〔i〕arrsort〔count1〕）｛
　　arrsort〔count〕arr〔i〕；
　　｝elseif（arr〔i〕arrsort〔0〕）｛
　　insert（arr，arrsort，arr〔i〕，0，count）；
　　｝else｛
　　for（intj0；jcount1；j）｛
　　if（arr〔i〕arrsort〔j〕arr〔i〕arrsort〔j1〕）｛
　　insert（arr，arrsort，arr〔i〕，j1，count）；
　　
　　｝
　　｝
　　｝
　　
　　｝
　　System。out。print（经过插入排序后：）；
　　for（inti0；i10；i）
　　System。out。print（arrsort〔i〕）；
　　System。out。println（）；
　　｝
　　publicvoidinsert（int〔〕arr，int〔〕arrsort，intvalue，intindex，intcount）｛
　　for（i）
　　arrsort〔i〕arrsort〔i1〕；
　　arrsort〔index〕
　　｝
　　publicvoidMergesort（int〔〕arr，intleft，intright）｛
　　if（rightleft0）｛
　　int〔〕arr1newint〔（rightleft）21〕；
　　int〔〕arr2newint〔（rightleft1）2〕；
　　intj0；
　　intk0；
　　for（i）｛
　　if（i（rightleft）2）｛
　　arr1〔j〕arr〔i〕；
　　｝else｛
　　arr2〔k〕arr〔i〕；
　　｝
　　｝
　　Mergesort（arr1，0，（rightleft）2）；
　　Mergesort（arr2，0，（rightleft1）2）；
　　Merge（arr1，arr2，arr）；
　　｝
　　｝
　　publicvoidMerge（int〔〕arr1，int〔〕arr2，int〔〕arr）｛
　　inti0；
　　intj0；
　　intk0；
　　intL1arr1。
　　intL2arr2。
　　while（iL1jL2）｛
　　if（arr1〔i〕arr2〔j〕）｛
　　arr〔k〕arr1〔i〕；
　　i；
　　｝else｛
　　arr〔k〕arr2〔j〕；
　　j；
　　｝
　　k；
　　｝
　　if（iL1）｛
　　for（jL2；j）
　　arr〔k〕arr2〔j〕；
　　｝else｛
　　for（iL1；i）
　　arr〔k〕arr1〔i〕；
　　｝
　　｝
　　｝
　　若有错误，麻烦指正，不胜感激。