算法_排序算法（冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、基数排序、堆排序）

拼搏现实的明天。 2023-07-10 14:28 35阅读 0赞

### 文章目录 ###

*   *  冒泡排序
     *  选择排序
     *  插入排序
     *  希尔排序
     *  快速排序
     *  归并排序
     *  基数排序
     *  堆排序
     *  常用排序算法总结和对比

## 冒泡排序 ##

1.  一共进行 `arr.length-1`次循环
2.  每轮中两两比较，前者比后者大交换，将最大值排到末尾，不参与下一轮排序
3.  如果发现在某轮排序中，没有发生一次交换， 可以提前结束冒泡排序

/**
     * 冒泡排序
     * @param arr
     */
    private static void BubbleSort(int[] arr) {
        
    	//控制比较轮数,两两比较，需要arr.length-1轮
    	for (int i = 0; i < arr.length - 1; i++) {
        
    		boolean flag = true;
    		//每轮中两两比较，前者比后者大交换
    		for (int j = 0; j < arr.length - 1 - i; j++) {
        
    			if (arr[j + 1] < arr[j]) {
        
    				int temp = arr[j];
    				arr[j] = arr[j + 1];
    				arr[j + 1] = temp;
    				flag = false;
    			}
    		}
    		//一轮中都没有出现交换，退出
    		if (flag) {
        
    			break;
    		}
    	}
    }

## 选择排序 ##

在n个数中找到最小（大）的放到最前（后）面，再在剩下的n-1个数中找到最小的放到第二个位置，以此类推，直到数组中只剩下一个元素。

/**
     * 选择排序
     * @param arr
     */
    private static void selectSort(int[] arr) {
        
    	//控制比较轮数,两两比较，需要arr.length-1轮
    	for (int i = 0; i < arr.length - 1; i++) {
        
    		int min = i;
    		//记录最小值索引
    		for (int j = i + 1; j < arr.length; j++) {
        
    			if (arr[j] < arr[min]) {
        
    				min = j;
    			}
    		}
    		//与当前轮首位交换
    		if (i != min) {
        
    			int temp = arr[i];
    			arr[i] = arr[min];
    			arr[min] = temp;
    		}
    	}
    }

## 插入排序 ##

把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

/**
     * 插入排序
     * @param arr
     */
    private static void insertSort(int[] arr) {
        
    	for (int i = 1; i < arr.length; i++) {
        
    		//待插入的数
    		int insertVal = arr[i];
    		//待插入索引
    		int insertIndex = i - 1;
    		// 给insertVal 找到插入的位置
    		while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
        
    			arr[insertIndex + 1] = arr[insertIndex];
    			insertIndex--;
    		}
    		// 当退出while循环时，说明插入的位置找到, insertIndex + 1
    		if (insertIndex + 1 != i) {
        
    			arr[insertIndex + 1] = insertVal;
    		}
    	}
    }

## 希尔排序 ##

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

/**
     * 希尔排序
     * @param arr
     */
    private static void shellSort(int[] arr) {
        
    	// 增量gap, 并逐步的缩小增量
    	for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        
    		//gap版插入排序
    		for (int i = gap; i < arr.length; i++) {
        
    			int insertVal = arr[i];
    			int insertIndex = i - gap;
    			while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
        
    				arr[insertIndex + gap] = arr[insertIndex];
    				insertIndex -= gap;
    			}
    			if (i != insertIndex) {
        
    				arr[insertIndex + gap] = insertVal;
    			}
    		}
    	}
    }

## 快速排序 ##

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

/**
     * 快速排序
     * @param arr
     * @param low
     * @param high
     */
    private static void quickSort(int[] arr, int low, int high) {
        
    	if (low < high) {
        
    		int pivot = getPivot(arr, low, high);
    		quickSort(arr, low, pivot - 1);
    		quickSort(arr, pivot + 1, high);
    	}
    }
    
    /**
     * 枢轴
     * @param arr
     * @param low
     * @param high
     * @return
     */
    private static int getPivot(int[] arr, int low, int high) {
        
    	int pivot = arr[low];
    	while (low < high) {
        
    		//如果枢轴定义为低位端，从高位端先遍历
    		while (low < high && arr[high] >= pivot) {
        
    			high--;
    		}
    		arr[low] = arr[high];
    		while (low < high && arr[low] <= pivot) {
        
    			low++;
    		}
    		arr[high] = arr[low];
    	}
    	//此时low=high,即为枢轴
    	arr[low] = pivot;
    	return low;
    }

## 归并排序 ##

采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

/**
     * 递归拆分+合并
     * @param arr
     * @param start
     * @param end
     * @param temp
     */
    private static void mergeSort(int[] arr, int start, int end, int[] temp) {
        
    	if (start < end) {
        
    		//中间索引
    		int mid = (start + end) / 2;
    		//向左递归分解
    		mergeSort(arr, start, mid, temp);
    		//向右递归分解
    		mergeSort(arr, mid + 1, end, temp);
    		//退栈合并
    		merge(arr, start, end, temp);
    	}
    }
    
    /**
     * 合并
     * @param arr
     * @param start
     * @param end
     * @param temp
     */
    private static void merge(int[] arr, int start, int end, int[] temp) {
        
    	int mid = (start + end) / 2;
    	int left = start;
    	int right = mid + 1;
    	int cur = 0;
    
    	//左右比较，有序添加到temp数组
    	while (left <= mid && right <= end) {
        
    		temp[cur++] = arr[left] <= arr[right] ? arr[left++] : arr[right++];
    	}
    	//添加剩余数据
    	while (left <= mid) {
        
    		temp[cur++] = arr[left++];
    	}
    	while (right <= end) {
        
    		temp[cur++] = arr[right++];
    	}
    
    	//temp数组复制到原数组
    	left = start;
    	cur = 0;
    	while (left <= end) {
        
    		arr[left++] = temp[cur++];
    	}
    }

## 基数排序 ##

*  基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用。
 *  基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法
 *  基数排序(Radix Sort)是桶排序的扩展
 *  将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

/**
     * 基数排序
     * @param arr
     */
    private static void radixSort(int[] arr) {
        
    	//查找最大数
    	int max = arr[0];
    	for (int i : arr) {
        
    		max = max > i ? max : i;
    	}
    	//得到最大位数
    	int maxLength = (max + "").length();
    	//定义二维桶数组
    	int[][] bucket = new int[10][arr.length];
    	//定义数组保存每个桶中的元素个数
    	int[] bucketECount = new int[10];
    	//放入桶
    	for (int i = 0; i < maxLength; i++) {
        
    		for (int j = 0; j < arr.length; j++) {
        
    			//取出对应位的值，按个十百...的顺序
    			int digit = (int) (arr[j] / Math.pow(10, i) % 10);
    			bucket[digit][bucketECount[digit]++] = arr[j];
    		}
    	}
    	//取出
    	int index = 0;
    	for (int i = 0; i < bucket.length; i++) {
        
    		if (bucketECount[i] != 0) {
        
    			for (int j = 0; j < bucketECount[i]; j++) {
        
    				arr[index++] = bucket[i][j];
    			}
    		}
    		bucketECount[i] = 0;
    	}
    }

## 堆排序 ##

*  堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆, 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。
 *  每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
 *  大顶堆特点：`arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2]` ， i 对应第几个节点，i从0开始编号
 *  小顶堆：`arr[i] <= arr[2*i+1] && arr[i] <= arr[2*i+2]`
 *  升序采用大顶堆，降序采用小顶堆

/**
     * 堆排序
     * @param arr
     */
    private static void heapSort(int[] arr) {
        
    	//将无序序列构成一个大顶堆
    	//完全二叉树最后一个非叶子节点为arr.length / 2 - 1
    	for (int i = arr.length / 2 - 1; i >= 0; i--) {
        
    		adjustHeap(arr, i, arr.length);
    	}
    	//首尾元素交换，排除最大元素后并重构
    	for (int i = arr.length - 1; i > 0; i--) {
        
    		int temp = arr[i];
    		arr[i] = arr[0];
    		arr[0] = temp;
    		adjustHeap(arr, 0, i);
    	}
    }
    
    /**
     * 将一个顺序存储二叉树（数组）调整为大顶堆
     * @param arr
     * @param i
     * @param length
     */
    private static void adjustHeap(int[] arr, int i, int length) {
        
    	int temp = arr[i];
    	//i的左节点2i+1，右节点2i+2
    	for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {
        
    		//挑出左右节点较大者
    		if (k + 1 < length && arr[k] < arr[k + 1]) {
        
    			k++;
    		}
    		//与待交换节点对比，谁大谁当父节点
    		if (arr[k] > temp) {
        
    			arr[i] = arr[k];
    			i = k;
    		} else {
        
    			break;
    		}
    	}
    	arr[i] = temp;
    }

## 常用排序算法总结和对比 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NoaWxsX0x5bg_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NoaWxsX0x5bg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200303201125700.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NoaWxsX0x5bg==,size_16,color_FFFFFF,t_70