图解Java经典算法冒泡选择插入希尔排序的原理与实现

第图解Java经典算法冒泡选择插入希尔排序的原理与实现目录一、冒泡排序1、基本介绍2、代码实现二、选择排序1、基本介绍2、代码实现三、插入排序1、基本介绍2、代码实现四、希尔排序1、基本介绍2、代码实现（交换排序）3、代码实现（移位排序）

一、冒泡排序

1、基本介绍

冒泡排序是重复地走访要排序的元素，依次比较两个相邻的元素，如果它们的顺序与自己规定的不符合，则把两个元素的位置交换。走访元素重复地进行，直到没有相邻元素需要交换为止，完成整个排序过程。

▶算法原理

1、比较相邻元素，如果前一个元素大于后一个元素，则交换。

2、依次向后对每一对相邻元素做同样的工作，直到队列末尾，第一轮过后最大的元素就位于最后一个元素位置了。

3、重复以上步骤，直到最后一个元素位置的前一位为止（因为最后一位已经排了）。

4、持续每次对越来越少的元素重复上面步骤，直到第一个元素和第二个元素交换后顺序为从大到小或从小到大，排序结束。

2、代码实现

冒泡排序实际上就是两个数两个数的比较，每循环一次将最大或最小的数放在最后，剩下的就继续两两比较。

publicstaticvoidbubbleSort(int[]arr){

//中间变量，用来交换数据

inttemp=0;

//外层循环

for(inti=0;iarr.length-1;i++){

//内层循环，每次找到最大的数后放在最后，下次遍历则会少一次，及arr.length-i-1

for(intj=0;jarr.length-i-1;j++){

//判断大小

if(arr[j]arr[j+1]){

//将两数进行交换

temp=arr[j];

arr[j]=arr[j+1];

arr[j+1]=temp;

}

二、选择排序

1、基本介绍

首先第一次确定第一个数为最小的，然后利用for循环，将第一个数后的数据遍历一遍，找是否还有比第一个数更小的，记录下来，遍历完毕后将第一个数与最小的数进行交换。然后又确定第二数，找第二个数以后的数，是否还有比第二个数更小的，找到后与第二个数又进行交换，重复上面即可。

以后的每次循环都是按照这种方式，直到最后两个数排完，数据就是有序的了。

2、代码实现

publicstaticvoidchoiceSort(int[]arr){

//用来记录最小的数

intarrData=0;

//记录最小的数的下标

intarrindx=0;

//外层循环，直到arr.length-1即可

for(inti=0;iarr.length-1;i++){

//首先把arr[i]当做最小的数，并记录下标

arrData=arr[i];

arrindx=i;

//内层循环，遍历i以后的数，找到比arr[i]还小的数

for(intj=i+1;jarr.length;j++){

//找到更小的数，就进行记录

if(arrDataarr[j]){

arrData=arr[j];

arrindx=j;

//循环完毕，说明找到了，最小的数，与arr[i]进行交换即可

arr[arrindx]=arr[i];

arr[i]=arrData;

}

三、插入排序

1、基本介绍

前面我们介绍的选择排序，找到最小的就与前面的进行交换。而插入排序，就是将确定的数的后一位插入到前面即可。图形介绍：

开始，id指向第一个数，mid指向第二个数，然后两个数进行比较。

此时，1比3小，但是3前面没数据了，于是将1插入到3的前面，注意这里是插入，不是交换。下一步3比5小，于是不用插入。

经过三次比较，确定了2的位置在1和3直接，直接将2插入。

又经过四次比较，找到0的位置在1的前面，于是将0插入到1的前面即可。

2、代码实现

publicstaticvoidinsertSort(int[]arr){

//下标为0的数是确定的，从下标为1开始循环

for(inti=1;iarr.length;i++){

//将下标为i的数暂存起来

intarrData=arr[i];

//从i-1开始往前循环

intarrIndx=i-1;

//判断退出的条件大于等于0

while(arrIndx=0){

//如果arrData大于下标为arrIndx的数，则位置找到，退出循环

if(arrDataarr[arrIndx]){

break;

//没有找到，就将前面的数往后移

arr[arrIndx+1]=arr[arrIndx];

arrIndx--;

//找到位置后，就将暂存的数据arrData插入到下标为arrIndx的位置

arr[arrIndx+1]=arrData;

}

四、希尔排序

1、基本介绍

首先将数组分为两组，3、2、0为一组，1、5为一组，g=arr.length/2。

2和3进行判断，3比2大，然后进行交换位置，交换后j=j-g0（因为第一次的分为两组，所以i-2）。所以i++，j=i-g

不需要交换，然后j=j-g0,所以i++，j=i-g

3比0大，需要交换。然后j=j-g0,j=j-g

交换后j=j-g0,i++arr.length了，第一轮结束

第二轮：在arr.length/2的基础上再除2，于是g=1；

然后两两交换，交换后进行j=j-g0的判断，不成立则i++,j=i-g，成立则j=j-g，就这样一直循环下去。第二轮后的结果：

第二轮结束后，g/2=0结果不大于0，所以排序结束

2、代码实现（交换排序）

publicstaticvoidshellSort_exchange(int[]arr){

//做中间变量，进行数据交换

inttemp=0;

//g首先数组总长除以2，然后每次除以2

for(intg=arr.length/2;gg/=2){

//i从g的位置开始遍历

for(inti=g;iarr.length;i++){

//j从i-g的位置开始向前遍历，j的位置由j-g来决定

for(intj=i-g;j=0;j-=g){

//判断下标(j+g)和下标j位置的数的大小，然后进行交换

if(arr[j+g]arr[j]){

//交换即可

temp=arr[j+g];

arr[j+g]=arr[j];

arr[j]=temp;

}

3、代码实现（移位排序）

移位排序的思想与前面的交换排序一样的，只是在交换数的方式上有变化。交换排序数的交换方式来自冒泡排序，而移位排序数的交换方式来自插入排序。

publicstaticvoidtest1(int[]arr){

//与前面一样，开始数组长度除以2，然后每次除以2

for(intg=arr.length/2;gg/=2){

//i从g位置开始，每次加一

for(inti=g;iarr.length;i++){

//定义j的位置为i

intj=i;

//将下标为i位置的数暂存起来

inttemp=arr[i];

//判断下标j位置的数和j-g位置的数，与前面一样

if(arr[j]arr[j-g]){