java实现四个常见的排序算法

╰+攻爆jí腚メ 2022-03-18 09:26 161阅读 0赞

package com.example.demo;
    
    import java.util.Arrays;
    
    public class SortTest {
    
    	/**
    	 * 冒泡法排序<br/>
    	 * <li>比较相邻的元素。如果第一个比第二个大，就交换他们两个。</li>
    	 * <li>对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。</li>
    	 * <li>针对所有的元素重复以上的步骤，除了最后一个。</li>
    	 * <li>持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。</li>
    	 */
    	public void bubbleSort(int[] a) {
    		int len = a.length;
    		int temp;
    		for (int i = 0; i < len; i++) {
    			for (int j = 0; j < len - i - 1; j++) {// 注意第二重循环的条件
    				if (a[j] > a[j + 1]) {
    					temp = a[j];
    					a[j] = a[j + 1];
    					a[j + 1] = temp;
    				}
    			}
    		}
    	}
    
    	/**
    	 * 选择排序<br/>
    	 * <li>在未排序序列中找到最小元素，存放到排序序列的起始位置</li>
    	 * <li>再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。</li>
    	 * <li>以此类推，直到所有元素均排序完毕。</li>
    	 * 
    	 * @param numbers
    	 */
    	public void selectSort(int[] a) {
    		int len = a.length;
    		for (int i = 0; i < len; i++) {// 循环次数
    			int value = a[i];
    			int position = i;
    			for (int j = i + 1; j < len; j++) {// 找到最小的值和位置
    				if (a[j] < value) {
    					value = a[j];
    					position = j;
    				}
    			}
    			a[position] = a[i];// 进行交换
    			a[i] = value;
    		}
    	}
    
    	/**
    	 * 插入排序<br/>
    	 * <li>从第一个元素开始，该元素可以认为已经被排序</li>
    	 * <li>取出下一个元素，在已经排序的元素序列中从后向前扫描</li>
    	 * <li>如果该元素（已排序）大于新元素，将该元素移到下一位置</li>
    	 * <li>重复步骤3，直到找到已排序的元素小于或者等于新元素的位置</li>
    	 * <li>将新元素插入到该位置中</li>
    	 * <li>重复步骤2</li>
    	 */
    	public void insertSort(int[] a) {
    		int len = a.length;// 单独把数组长度拿出来，提高效率
    		int insertNum;
    		for (int i = 1; i < len; i++) {// 因为第一次不用，所以从1开始
    			int index = i;// 要插入的位置
    			insertNum = a[i];
    			for (int j = i - 1; j >= 0; j--) {
    				if (insertNum >= a[j]) {
    					break;
    				}
    				a[j + 1] = a[j];
    				index = j;
    			}
    			a[index] = insertNum;
    		}
    	}
    
    	
    	/**
    	 * 快速排序<br/>
    	 * <li>从数列中挑出一个元素，称为“基准”</li>
    	 * <li>重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，
    	 * 该基准是它的最后位置。这个称为分割（partition）操作。</li>
    	 * <li>递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。</li>
    	 * @param numbers
    	 * @param start
    	 * @param end
    	 */
    	public static void quickSort(int[] numbers, int start, int end) {
    		if (start < end) {
    			int base = numbers[start]; // 选定的基准值（第一个数值作为基准值）
    			int temp; // 记录临时中间值
    			int i = start, j = end;
    			do {
    				while ((numbers[i] < base) && (i < end))
    					i++;
    				while ((numbers[j] > base) && (j > start))
    					j--;
    				if (i <= j) {
    					temp = numbers[i];
    					numbers[i] = numbers[j];
    					numbers[j] = temp;
    					i++;
    					j--;
    				}
    			} while (i <= j);
    			if (start < j) {
    				quickSort(numbers, start, j);
    			}
    			if (end > i) {
    				quickSort(numbers, i, end);
    			}
    		}
    	}
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int[] array = { 37, 47, 23, 100, 19, 56, 56, 99, 9 };
    		SortTest st = new SortTest();
    		// st.bubbleSort(array);
    		// st.selectSort(array);
    		st.insertSort(array);
    		// st.quickSort(array, 0, array.length - 1);
    		System.out.println("排序后：" + Arrays.toString(array));
    	}
    }

冒泡排序动态演示：[https://www.runoob.com/w3cnote/bubble-sort.html][https_www.runoob.com_w3cnote_bubble-sort.html]

插入排序动态演示：[https://www.runoob.com/w3cnote/insertion-sort.html][https_www.runoob.com_w3cnote_insertion-sort.html]

选择排序动态演示：[https://www.runoob.com/w3cnote/selection-sort.html][https_www.runoob.com_w3cnote_selection-sort.html]

快速排序动态演示：[https://www.runoob.com/w3cnote/quick-sort-2.html][https_www.runoob.com_w3cnote_quick-sort-2.html]

[https_www.runoob.com_w3cnote_bubble-sort.html]: https://www.runoob.com/w3cnote/bubble-sort.html
[https_www.runoob.com_w3cnote_insertion-sort.html]: https://www.runoob.com/w3cnote/insertion-sort.html
[https_www.runoob.com_w3cnote_selection-sort.html]: https://www.runoob.com/w3cnote/selection-sort.html
[https_www.runoob.com_w3cnote_quick-sort-2.html]: https://www.runoob.com/w3cnote/quick-sort-2.html