三种简单的排序算法

喜欢ヅ旅行 2022-05-19 13:13 218阅读 0赞

**1、选择排序**

**选择排序的思想：**第一次从R\[0\]~R\[n-1\]中选取最小值，与R\[0\]交换，第二次从R[1][]~R\[n-1\]中选取最小值，与R[1][]交换，….，第i次从R\[i-1\]~R\[n-1\]中选取最小值，与R\[i-1\]交换，…..，第n-1次从R\[n-2\]~R\[n-1\]中选取最小值，与R\[n-2\]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。实现如下：

public static void selectSort(int[] arr) {
    		// 确定0~arr.length-2，i表示的是索引，所以i的范围不能乱变
    		for (int i = 0; i < arr.length - 1; i++) {
    			// i之后的所有元素的索引是i+1~arr.length-1
    			for (int j = i + 1; j < arr.length; j++) {
    				if (arr[i] > arr[j]) {
    					int temp = arr[i];
    					arr[i] = arr[j];
    					arr[j] = temp;
    				}
    			}
    		}
    	}

**2、冒泡排序**

**冒泡排序的思想：**根据序列中两个元素的比较结果来对换这两个记录在序列中的位置，将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。因此，每一趟都将较小的元素移到前面，较大的元素自然就逐渐沉到最后面了，也就是说，最大的元素最后才能确定，这就是冒泡。其实现如下：

public static void bubbleSort(int[] arr) {// 从小到大
    		// 一共需要循环arr.length-1次，i代表循环的次数
    		for (int i = 0; i < arr.length - 1; i++) {
    			// 每次循环都对arr.length-1的元素进行比较，其中每比较i次，就说明已经有i个最值比较出来了，就不用再进行比较
    			for (int j = 0; j < arr.length - 1 - i; j++) {
    				if (arr[j] > arr[j + 1]) {
    					int temp = arr[j];
    					arr[j] = arr[j + 1];
    					arr[j + 1] = temp;
    				}
    			}
    		}
    	}

**3、插入排序**

**插入排序的思想：**当插入第i(i>=1)个元素时，前面的V\[0\],…,V\[i-1\]等i-1个 元素已经有序。这时，将第i个元素与前i-1个元素V\[i-1\]，…，V\[0\]依次比较，找到插入位置即将V\[i\]插入，同时原来位置上的元素向后顺移。在这里，插入位置的查找是顺序查找。其实现如下：

public static void insertSort(int[] arr) {
    		// i=1是因为i在这里代表了要比较的数字的位置，排序时从后往前排序，所以要为1
    		for (int i = 1; i < arr.length; i++) {
    			// j=i，j--，使要比较的两个数字两两往前比较
    			for (int j = i; j > 0; j--) {// 如果后面的数字大于前面的，就插入数字
    				if (arr[j] < arr[j - 1]) {
    					int temp = arr[j];
    					arr[j] = arr[j - 1];
    					arr[j - 1] = temp;
    				}
    			}
    		}
    	}

[1]: http://static.zybuluo.com/Rico123/ymihfm526o5xv5bo1btvm1fy/%E5%85%AB%E5%A4%A7%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93.jpg