Java----冒泡排序、选择排序、插入排序、快速排序、堆排序

int[] arr = {4, 2, 7, 1, 5, 9, 3, 6, 8}; 冒泡排序

for(int i = 0; i < arr.length-1; i++) //外循环是控制排序的次数n-1, 每次循环结束确定一个最大值 { for(int j = 0; j < arr.length - 1 - i; j++) // 内循环是第i次循环中比较的次数n-i { if(arr[j] > arr[j+1]){//前面一个和后面一个相互比较，较大的和较小的交换位置，较小的排前面，本次循环完成之后最大的放最后 int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } }

插入排序

for(int i = 1; i < arr.length; i++) //外循环是1到n-1，左边取出数组第0个元素作为已经排序数组，接着i从数组中第1元素个开始循环 { int k=arr[i];//取出arr[i]保存到k int j=i-1;//arr[i]前面的那个元素 while(j>=0 && arr[j]>k) { arr[j+1]=arr[j];//左边的元素向右覆盖后面的元素 j--;//一直向左比较 } arr[j+1]=k;//找到位置插入 }

选择排序

for(int i = 0; i < arr.length; i++) //外循环是0到n-1，每次挑选出最小的元素，一共需要挑选n-1次 { int index=i;//保存待排序元素中最小的下标 for(int j=i+1;j<arr.length;j++) { if(arr[j]<=arr[index]) {//找到待排序中最小的 index=j; } } //arr[index]和待排序中的第一个arr[i]交换 int temp=arr[i]; arr[i]=arr[index]; arr[index]=temp; }

计数排序 int[] arr = {0,2，5,3，7,9，3,3，3,7}

// 找到待排序数组中的最大值 int max = Arrays.stream(arr).max().getAsInt(); // 创建计数数组，并初始化为 0 int[] countArray = new int[max + 1]; for (int i = 0; i < countArray.length; i++) { countArray[i] = 0; } // 统计数组中每个元素的出现次数 for (int i = 0; i < arr.length; i++) { countArray[array[i]]++; } // 计算每个元素在排序后的序列中的位置 for (int i = 1; i < countArray.length; i++) { countArray[i] += countArray[i - 1]; } // 创建一个临时数组存储排序结果 int[] tempArray = new int[arr.length]; for (int i = array.length - 1; i >= 0; i--) { tempArray[countArray[arr[i]] - 1] = arr[i]; countArray[arr[i]]--; } // 将临时数组的内容复制回原始数组 for (int i = 0; i < arr.length; i++) { arr[i] = tempArray[i]; }

归并排序 使用递归方式，将数组对半分，再对半分（如：8—4—2—1），直到为一个不能再分，再排序合并（如：1–2–4–8）

package gg; public class Solution { public static void main(String args[]) { int[] arr = {1,5,3,4,7,8,9,6,2,0}; System.out.print("排序前的数组为："); for(int i = 0; i < arr.length; i++){ System.out.print(arr[i] + " "); } merge_sort(arr); System.out.println(); System.out.print("排序后的数组为："); for(int i = 0; i < arr.length; i++){ System.out.print(arr[i] + " "); } } static void merge_sort_recursive(int[] arr, int[] result, int start, int end) { // 1、分解到最小需要解决的地步，无法再分解了 if (start >= end){ // 需要开始解决问题 return; } // 2、解决 // 计算数组 arr 的中间位置 int mid = (start + end ) / 2; // start1 为左区间的开始位置 int start1 = start; // end1 为左区间的结束位置 int end1 = mid; // start2 为右区间的开始位置 int start2 = mid + 1; // end2 为右区间的结束位置 int end2 = end; // 调用 merge_sort_recursive 函数，将 arr 数组中的 start1 到 end1 这一区间的数字排序后，并存放到 result 中 merge_sort_recursive(arr, result, start1, end1); // 调用 merge_sort_recursive 函数，将 arr 数组中的 start2 到 end2 这一区间的数字排序后，并存放到 result 中 merge_sort_recursive(arr, result, start2, end2); // 3、合并 // 将左右区间中较小的数字存放到 result 中，从 k 开始 int k = start; while (start1 <= end1 && start2 <= end2){ // 如果 arr[start1] < arr[start2]) if(arr[start1] < arr[start2]){ // result[k] 存放的是 arr[start1] result[k] = arr[start1] ; start1++; k++; }else{ // 否则，result[k] 存放的是 arr[start2] result[k] = arr[start2] ; start2++; k++; } } // 如果左区间中还有元素，那么把它都添加到 result 中 while (start1 <= end1){ result[k] = arr[start1]; k++; start1++; } // 如果右区间中还有元素，那么把它都添加到 result 中 while (start2 <= end2){ result[k] = arr[start2]; k++; start2++; } // 最后，把结果赋值到 arr 中 for (k = start; k <= end; k++) arr[k] = result[k]; } public static void merge_sort(int[] arr) { int len = arr.length; int[] result = new int[len]; merge_sort_recursive(arr, result, 0, len - 1); } }

快速排序

package gg; import java.util.Arrays; public class Solution { public static void main(String args[]) { int[] nums = {1,5,1,8,2,2,4,2,2,3}; // 打印排序前的数组 System.out.println(Arrays.toString(nums)); // 执行快速排序操作 quickSort(nums,0,nums.length - 1); // 打印排序后的数组 System.out.println(Arrays.toString(nums)); } // 函数传入待排序数组 nums // 排序区间的左端点 left // 排序区间的右端点 right private static void quickSort(int[] nums,int left, int right){ // 如果 left 大于等于 right，说明该区间只有 1 个或者没有元素 if( left >=right ){ // 无需再递归划分后再排序，直接返回 return; } // 调用函数 partition，将 left 和 right 之间的元素划分为左右两部分 int mid = partition(nums,left,right); // 划分之后，再对 mid 左侧的元素进行快速排序 quickSort(nums,left,mid - 1); // 划分之后，再对 mid 右侧的元素进行快速排序 quickSort(nums,mid + 1,right); } private static int partition(int[] nums, int left ,int right){ // 经典快速排序的写法 // 设置当前区间的第一个元素为基准元素 int pivot = nums[left]; // left 向右移动，right 向左移动，直到 left 和 right 指向同一元素为止 while( left < right ){ // 只有当遇到小于 pivot 的元素时，right 才停止移动 // 此时，right 指向了一个小于 pivot 的元素，这个元素不在它该在的位置上 while( left < right && nums[right] >= pivot ){ // 如果 right 指向的元素是大于 pivot 的，那么 // right 不断的向左移动 right--; } // 将此时的 nums[left] 赋值为 nums[right] // 执行完这个操作，比 pivot 小的这个元素被移动到了左侧 nums[left] = nums[right]; // 只有当遇到大于 pivot left 才停止移动 // 此时，left 指向了一个大于 pivot 的元素，这个元素不在它该在的位置上 while( left < right && nums[left] <= pivot){ // 如果 left 指向的元素是小于 pivot 的，那么 // left 不断的向右移动 left++; } // 将此时的 nums[right] 赋值为 nums[left] // 执行完这个操作，比 pivot 大的这个元素被移动到了右侧 nums[right] = nums[left]; } // 此时，left 和 right 相遇，那么需要将此时的元素设置为 pivot // 这个时候，pivot 的左侧元素都小于它，右侧元素都大于它 nums[left] = pivot; // 返回 left return left; } }

堆排序

package gg; import java.util.Arrays; public class Solution { public static void main(String args[]) { int[] arr = {1,5,1,8,7,6,4,2,2,3}; // 打印排序前的数组 System.out.println(Arrays.toString(arr)); // 执行堆排序操作 heapSort(arr); // 打印排序后的数组 System.out.println(Arrays.toString(arr)); } public static void heapSort(int[] arr){ // 1、将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆 for(int i = arr.length / 2 - 1 ; i >= 0 ; i-- ){ //从第一个非叶子节点从下至上，从后向前调整结构 adjustHeap( arr , i , arr.length ); } // 2、将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端，此时数组末端存储了当前区间最大的元素 for(int j = arr.length - 1 ; j > 0 ; j-- ){ // 3、每次将堆顶元素与末尾元素进行交换，使末尾元素最大 swap(arr,0,j); // 4、重新对堆进行调整 adjustHeap(arr,0,j); // 执行完 4 之后，剩下未排序的那些元素依旧维护着一个最大堆，继续下一轮循环 } } // 调整大顶堆 public static void adjustHeap(int []arr,int parent,int length){ // 1、取出当前元素，需要把它挪到正确的位置上，比如此时是 A 元素 // A // / \ // B C int temp = arr[parent]; // 2、从 parent 节点的左子节点开始 // 也就是 2 * parent + 1 处开始 int child = 2 * parent + 1 ; while(child < length){ // A // / \ // B C // 获取 A 、B 、C 三者的最大值，把它放到 A 位置 // 于是，第一步先去对比 B 和 C，查看它们的较大值是哪一个 // 3、如果左子节点小于右子节点，child 指向右子节点 if( child + 1 < length && arr[child] < arr[ child + 1 ] ){ child++; } // 如果父节点的值已经大于孩子节点的值，说明在正确位置上 // 直接结束 if (temp >= arr[child]){ break; } // B 、 C 都是 A 的子节点，如果 B 、 C 的较大值大于 A // 将最大值赋值给 A arr[parent] = arr[child]; // 此时，parent 这个节点已经存放了正确的元素 // B // / \ // B C // 接下来，需要观察一下，parent 原先的节点值 A 应该放到哪个位置 // 所以，顺着 parent 这个节点来到它的子节点，就是 B 这个节点的位置，也是 child 这个节点的位置 parent = child; // 那么，子节点也发生了变化，从它的左子节点开始 child = 2 * parent + 1; } // 将 temp 值放到最终的位置 arr[parent] = temp; } // 交换元素 public static void swap(int []arr,int a ,int b){ int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } }