【JAVA】面试须知的五种排序算法0917_思路及实现（所有代码亲测可用）

﹏ヽ暗。殇╰゛Y 2021-09-24 16:36 91阅读 0赞

### 文章目录 ###

*  1.冒泡排序
 *   *  1.1 思路
     *  1.2 JAVA代码
 *  2.选择排序
 *   *  2.1 思路
     *  2.2 JAVA代码
     *   *  方法一
         *  方法二(改进)
 *  3.插入排序
 *   *  3.1 思路
     *  3.2 JAVA代码
     *   *  方法一（代码不可用）
         *  方法二（修改方法一，使代码可用）
 *  4.快速排序
 *   *  4.1 思路
     *  4.2 JAVA代码
 *  5.归并排序
 *   *  5.1 思路
     *  5.2 JAVA代码

# 1.冒泡排序 #

## 1.1 思路 ##

冒泡排序：  
1.外循环，循环n次，每次循环获取最大值，放在最后，新序列为将最大值去除的序列。  
2.内循环中，对每一对相邻元素进行比较，对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数。从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数

## 1.2 JAVA代码 ##

class Solution { 
    	public int[] bubbleSort(int[] arr) { 
    		int n = arr.length;
    		if (n == 0) { return arr;}
    		/*循环n次，依次将最大、第二、第三放在数组的最后。 当循环第n次的时候（即i=n-1），内循环不执行(即j>=n-1-i)。 */
    		for (int i = 0; i < n; i++) { 
    			for (int j = 0;j < n-1-i; j++) { 
    				if (arr[j+1] < arr[j]) { 
    					int tmp = arr[j];
    					arr[j] = arr[j+1];
    					arr[j+1] = tmp;
    				}
    			}
    		}
    		return arr;
    	}
    }

IDEA执行结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODg1MTk3MA_size_16_color_FFFFFF_t_70_pic_center]

# 2.选择排序 #

## 2.1 思路 ##

两种实现方式的差别在于：在发现比当前小的数时，是否发生交换。标准的方式是不交换的，只是记录了较小的数对应的下标，遍历结束之后，再进行交换。

## 2.2 JAVA代码 ##

### 方法一 ###

class Solution { 
    	public int[] selectionSort(int[] a) { 
    		int n = a.length;
    		for (int i = 0; i < n-1; i++) { 
    			for (int j = i+1; j < n; j++) { 
    				if(a[i] > a[j]) { 
    					int tmp = a[i];
    					a[i] = a[j];
    					a[j] = tmp;
    				}	
    			}	
    		}
    	}
    }

IDEA执行结果  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODg1MTk3MA_size_16_color_FFFFFF_t_70_pic_center 1]

### 方法二(改进) ###

class Solution { 
    	public int[] selectionSort(int[] a) { 
    		int n = a.length;
    		for (int i = 0; i < n-1; i++) { 
    			int min = i;
    			for (int j = i+1; j < n; j++) { 
    				if(a[min] > a[j]) { 
    					min = j;
    				}	
    			}
    			if (min != i) { 
    				int tmp = a[min];
    				a[min] = a[i];
    				a[i] = tmp;
    			}	
    		}
    	}
    }

IDEA执行结果  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODg1MTk3MA_size_16_color_FFFFFF_t_70_pic_center 2]

# 3.插入排序 #

## 3.1 思路 ##

对于未排序数据，在已排序序列中从后向前扫描。  
代码实现：  
1.首先，要循环n-1次。n为数组长度。  
2.拿出一块内存空间放置即将要与已排序序列比较的那个数tmp。  
3.比较过程：  
将未排序的第一个数tmp与已排序序列中的数（preIndex对应的值）倒序一一比较，直到tmp大于其中的某一个数或者preIndex=0。  
满足条件，a\[preIndex+1\] = a\[preIndex\], preIndex–;  
不满足条件，a\[preIndex+1\] = tmp;

## 3.2 JAVA代码 ##

错误代码：错误原因在于：每一次循环，都把拿出来的值又放回了原来的地方，实际上应该放在j的地方。

### 方法一（代码不可用） ###

class Solution { 
    	public int[] insertionSort(int[] a) { 
    		int n = a.length;
    		if (n == 0) { return a;}
    		for (int i = 1; i < n; i++) { 
    			int tmp = a[i];
    			for (int j = i-1; j >= 0 && a[j] < tmp; j--) { 
    					a[j+1] = a[j];
    				}
    			a[i] = tmp; //错误主要原因：将tmp的值又放在了拿出来的位置，实际上应该放在j的位置。
    		}
    		return a;
    	}
    }

### 方法二（修改方法一，使代码可用） ###

class Solution { 
        //测试用例
        public static void main(String[] args){ 
            int[] a = { 3,5,8,22,6,7,9,0,2};
            // int[] a = {};
            // int[] a = {1};
            insertionSort(a);
            System.out.println(Arrays.toString(a));
        }
    
    	
        private static void insertionSort(int[] a) { 
            if (a.length > 0) { 
                for (int i = 1; i < a.length; i++) { 
                    int tmp = a[i];
                    int j = i - 1;
                    while(j >= 0 && tmp < a[j])  { 
                        a[j + 1] = a[j--];
                    }
                    a[j+1] = tmp;
                }
            }
        }
    }

IDEA执行结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODg1MTk3MA_size_16_color_FFFFFF_t_70_pic_center 3]

# 4.快速排序 #

快速排序思想:`分治法`、`双指针`、`递归`

## 4.1 思路 ##

*  设定一个基准数。如a\[0\]，也可以从数组中随机挑选一个值作为基准数，并将基准数放在数组的最后
 *  左右指针。首先右指针向前移动找到比基准数小的数，然后左指针向后移动找到比基准数大的数，交换。直到左右指针相遇（i=j）
 *  基准数左边的序列和右边的序列分别作为新的序列进行递归。

## 4.2 JAVA代码 ##

import java.util.Arrays;
    
    class Solution { 
        public static void main(String[] args){ 
            // int[] a = {3,5,8,22,6,7,9,0,2};
            int[] a = { };
            // int[] a = {1};
            sort(a);
            System.out.println(Arrays.toString(a));
        }
    
        public static void sort(int[] a){ 
            if (a.length > 0 ) { 
                quickSort(a, 0, a.length-1);
            }
        }
    
        private static void quickSort(int[] a, int left, int right){ 
            int smallIndex = partition(a, left, right);
            if (smallIndex > left) { 
                quickSort(a, left, smallIndex - 1);
            }
            if (smallIndex < right) { 
                quickSort(a, smallIndex + 1, right);
            }
        }
    
        private static int partition(int[] a, int left, int right) { 
            int i = left,j = right;  //左右指针
            int tmp = a[left];   // 基准值
            while (i < j) { 
                //从右向左找比基准值小的，找到第一个之后(下标为j)，退出循环
                while (a[j] >= tmp && i < j) { 
                    j--;
                }
                //从左想右找比基准值大的，找到第一个后（下标为i），退出循环
                while (a[i] <= tmp && i < j) { 
                    i++;
                }
                //交换这两个数在数组的位置
                swap(a, i, j);
            }
            //将基准值放在中间位置。
            swap(a,left,i);
            return i;
        }
        //交换函数
        private static void swap(int[] array, int i, int j) { 
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }

import java.util.Arrays
    
    class Solution { 
    	//测试用例
        public static void main(String[] args){ 
            // int[] a = {3,5,8,22,6,7,9,0,2};
            // int[] a = {};
            int[] a = { 1};
            sort(a);
            System.out.println(Arrays.toString(a));
        }
    	
        public static void sort(int[] a){ 
            quickSort(a, 0, a.length-1);
        }
    
        public static void quickSort(int[] a, int left, int right) { 
            if (left  < right) { 
                int i = left, j = right;
                int tmp = a[left];   // 基准值，将该值保存，数组中不需要留存，补这个值的窟窿
                //int tmp =
                while (i < j) { 
                    // 从右向左找小于x的数来填s[i]
                    while (a[j] >= tmp && i < j) { 
                        j--;
                    }
                    if(i < j) { 
                        a[i++] = a[j];
                    }
                    // 从左向右找大于或等于x的数来填s[j]
                    while (a[i] <= tmp && i < j) { 
                        i++;
                    }
                    if(i < j) { 
                        a[j--] = a[i];
                    }
                }
                //退出时，i等于j。将x填到这个坑中。
                a[i] = tmp;
                quickSort(a, left, i-1);
                quickSort(a, i+1, right);
            }
        }
    }

# 5.归并排序 #

思想：`分治法`、`递归`  
分治法：

*  分割，递归地把当前序列平均分割成两半
 *  归并，在保持元素顺序的同时将上一步得到的子序列集成到一起

## 5.1 思路 ##

归并操作：  
递归法（Top-down）  
1.申请空间，使其大小为为两个已经排序序列之和，该空间用来存放合并后的序列。  
2.设定两个指针，最初位置分别为两个已经排序序列的起始位置  
3，比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一个位置  
4.重复步骤3直到某一指针到达序列尾  
5.将另一序列剩下的所有元素直接复制到合并序列尾。

## 5.2 JAVA代码 ##

import java.util.Arrays;
    
    class Solution { 
    	//测试用例
    	public static void main(String[] args) { 
    		int[] arr= { 9,8,7,6,5,4,3,2,1};
    		mergeSort(arr);
    		System.out.println(Arrays.toString(arr));
    	} 
    	/* 分割：输入为一个数组，输出为两个数组，循环调用该函数进行分割,直至最小粒度，然后向上归并。 整体输出：一个已经归并好的数组。 进行了几次分割，就进行了几次归并 */
    	public int[] mergeSort(int[] arr) { 
    		int mid = arr.length/2;
    		int[] left = Arrays.copyOfRange(arr, 0, mid); //arr[0]-arr[mid-1]
    		int[] right = Arrays.copyOfRange(arr, mid, arr.length);   //arr[mid]-arr[arr.length-1]
    		return merge(mergeSort(left), mergeSort(right)); 
    	}
    	/* 归并函数：对于分割的两个数组，进行归并。 */
    	public static int[] merge(int[] left, int[] right) { 
    		int[] result = new int[left.length+right.length];
    		for(int index=0,i = 0,j = 0; index < result.length; index++) { 
    			if (i >= left.length)
    				result[index] = right[j++];
    			else if (j >= right.length)	
    				result[index] = left[i++];
    			else if (left[i] < right [j])
    				result[index] = left[i++];
    			else 
    				result[index] = right[j++];
    		}
    		return result;		
    }

不知道为毛，结果不对。。。。。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODg1MTk3MA_size_16_color_FFFFFF_t_70_pic_center 4]  
以下代码亲测可用！！！

class Solution { 
    	//测试用例
        public static void main(String[] args) { 
            int[] a = { 1};			//测试用例1
            //int[] a = {}; //测试用例2
            //int[] a = {1,4,7,3,9,2,6,7,8}; //测试用例3
            sort(a);
            System.out.println(Arrays.toString(a));
        }
        
    	//排序，特殊处理不需要排序的数组；其他情况将数组和数组的首尾下标作为参数传给分离函数
        public static void sort(int[] a){ 
            if (a.length <= 1) { 
                System.out.println("数组不需要排序");
            }else{ 
                mergeSort(a, 0, a.length-1);
            }
        }
    	
        public static void mergeSort(int[] a, int L, int R) { 
            // 当切分到只剩一个元素的时候，就不会执行
            // 只有当剩下的元素大于1个的时候才执行下面代码
            if (L != R) { 
                // 换分切分点
                int M = (L + R) / 2;
                // 对左边进行归并
                mergeSort(a, L, M);
                // 对右边进行归并
                mergeSort(a, M + 1, R);
                // 合并左右两边
                merge(a, L, M, R);
            }
        }
    
        public static void merge(int[] a, int L, int M, int R) { 
            int i = L;//左序列指针
            int j = M+1;//右序列指针
            int t = 0;//临时数组指针
            int[] temp = new int[R-L+1];
            while (i<=M && j<=R){ 
                if(a[i]<=a[j]){ 
                    temp[t++] = a[i++];
                }else { 
                    temp[t++] = a[j++];
                }
            }
            while(i<=M){ //将左边剩余元素填充进temp中
                temp[t++] = a[i++];
            }
            while(j<=R){ //将右序列剩余元素填充进temp中
                temp[t++] = a[j++];
            }
            t = 0;
            //将temp中的元素全部拷贝到原数组中
            while(L <= R){ 
                a[L++] = temp[t++];
            }
    
        }
    }

IDEA执行结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODg1MTk3MA_size_16_color_FFFFFF_t_70_pic_center 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODg1MTk3MA_size_16_color_FFFFFF_t_70_pic_center 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODg1MTk3MA_size_16_color_FFFFFF_t_70_pic_center 7]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODg1MTk3MA_size_16_color_FFFFFF_t_70_pic_center]: /images/20210923/ec10e1de534d4c19aa70eaae9deae3f5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODg1MTk3MA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20210923/656a5c61dcfa40bbabd2316a010f84ee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODg1MTk3MA_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20210923/8ac5bd13575249419858f88f896d7109.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODg1MTk3MA_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20210923/63af5989be424354ade5cbb1f0dc953e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODg1MTk3MA_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20210923/feda196898de43be9372903b14a59623.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODg1MTk3MA_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20210923/460a84e9ecbc42c39a77c39aa4f2db91.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODg1MTk3MA_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20210923/a870e70d4fb146669d1092bade74d076.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODg1MTk3MA_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20210923/08e03d420952431897e0c61724fc5c35.png