做个医院网站多少钱,网站建设与开发教学大纲,公司网站建设内容,阿里巴巴数据分析官网本文主要介绍Java的七种常见排序算法的实现#xff0c;对选择排序、插入排序、冒泡排序、归并排序、快速排序、希尔排序、最小堆排序进行原理分析与实例介绍#xff0c;下面一起来看一下吧#xff1a; 一、选择排序(SelectSort) 基本原理#xff1a;对于给定的一组记录对选择排序、插入排序、冒泡排序、归并排序、快速排序、希尔排序、最小堆排序进行原理分析与实例介绍下面一起来看一下吧 一、选择排序(SelectSort) 基本原理对于给定的一组记录经过第一轮比较后得到最小的记录然后将该记录与第一个记录的位置进行交换接着对不包括第一个记录以外的其他记录进行第二次比较得到最小的记录并与第二个记录进行位置交换重复该过程直到进行比较的记录只有一个为止。 public class SelectSort { public static void selectSort(int[] array) { int i; int j; int temp; int flag; for (i 0; i array.length; i) { temp array[i]; flag i; for (j i 1; j array.length; j) { if (array[j] temp) { temp array[j]; flag j; } } if (flag ! i) { array[flag] array[i]; array[i] temp; } } } public static void main(String[] args) { int[] a { 5, 1, 9, 6, 7, 2, 8, 4, 3 }; selectSort(a); for (int i 0; i a.length; i) { System.out.print(a[i] ); } } } 二、插入排序(InsertSort) 基本原理对于给定的一组数据初始时假设第一个记录自成一个有序序列其余记录为无序序列。接着从第二个记录开始按照记录的大小依次将当前处理的记录插入到其之前的有序序列中直至最后一个记录插入到有序序列中为止。 public class InsertSort { public static void insertSort(int[] a) { if (a ! null) { for (int i 1; i a.length; i) { int temp a[i]; int j i; if (a[j - 1] temp) { while (j 1 a[j - 1] temp) { a[j] a[j - 1]; j--; } } a[j] temp; } } } int[] a { 5, 1, 7, 2, 8, 4, 3, 9, 6 }; // int[] a null; insertSort(a); } } } 三、冒泡排序(BubbleSort) 基本原理对于给定的n个记录从第一个记录开始依次对相邻的两个记录进行比较当前面的记录大于后面的记录时交换位置进行一轮比较和换位后n个记录中的最大记录将位于第n位然后对前(n-1)个记录进行第二轮比较重复该过程直到进行比较的记录只剩下一个为止。 public class BubbleSort { public static void bubbleSort(int array[]) { int temp 0; int n array.length; for (int i n - 1; i 0; i--) { for (int j 0; j i; j) { if (array[j] array[j 1]) { array[j] array[j 1]; array[j 1] temp; } } } } int a[] { 45, 1, 21, 17, 69, 99, 32 }; bubbleSort(a); } } } 四、归并排序(MergeSort) 基本原理利用递归与分治技术将数据序列划分成为越来越小的半子表再对半子表排序最后再用递归方法将排好序的半子表合并成为越来越大的有序序列。对于给定的一组记录(假设共有n个记录)首先将每两个相邻的长度为1的子序列进行归并得到n/2(向上取整)个长度为2或1的有序子序列再将其两两归并反复执行此过程直到得到一个有序序列。 public class MergeSort { public static void merge(int array[], int p, int q, int r) { int i, j, k, n1, n2; n1 q - p 1; n2 r - q; int[] L new int[n1]; int[] R new int[n2]; for (i 0, k p; i n1; i, k) L[i] array[k]; for (i 0, k q 1; i n2; i, k) R[i] array[k]; for (k p, i 0, j 0; i n1 j n2; k) { if (L[i] R[j]) { array[k] L[i]; i; } else { array[k] R[j]; j; } } if (i n1) { for (j i; j n1; j, k) array[k] L[j]; } if (j n2) { for (i j; i n2; i, k) { array[k] R[i]; } } } public static void mergeSort(int array[], int p, int r) { if (p r) { int q (p r) / 2; mergeSort(array, p, q); mergeSort(array, q 1, r); merge(array, p, q, r); } } int a[] { 5, 4, 9, 8, 7, 6, 0, 1, 3, 2 }; mergeSort(a, 0, a.length - 1); for (int j 0; j a.length; j) { System.out.print(a[j] ); } } } 五、快速排序(QuickSort) 基本原理对于一组给定的记录通过一趟排序后将原序列分为两部分其中前一部分的所有记录均比后一部分的所有记录小然后再依次对前后两部分的记录进行快速排序递归该过程直到序列中的所有记录均有序为止。 public class QuickSort { public static void sort(int array[], int low, int high) { int i, j; int index; if (low high) return; i low; j high; index array[i]; while (i j) { while (i j index array[j]) j--; if (i j) array[i] array[j]; while (i j index array[i]) i; if (i j) array[j--] array[i]; } array[i] index; sort(array, low, i - 1); sort(array, i 1, high); } public static void quickSort(int array[]) { sort(array, 0, array.length - 1); } int a[] { 5, 8, 4, 6, 7, 1, 3, 9, 2 }; quickSort(a); } } } 六、希尔排序(ShellSort) 基本原理先将待排序的数组元素分成多个子序列使得每个子序列的元素个数相对减少然后对各个子序列分别进行直接插入排序待整个待排序序列基本有序后最后再对所有元素进行一次直接插入排序。 public class ShellSort { public static void shellSort(int[] a) { int len a.length; int i, j; int h; int temp; for (h len / 2; h 0; h h / 2) { for (i h; i len; i) { temp a[i]; for (j i - h; j 0; j - h) { if (temp a[j]) { a[j h] a[j]; } else break; } a[j h] temp; } } } int a[] { 5, 4, 9, 8, 7, 6, 0, 1, 3, 2 }; shellSort(a); } } } 七、最小堆排序(MinHeapSort) 基本原理对于给定的n个记录初始时把这些记录看作一颗顺序存储的二叉树然后将其调整为一个小顶堆然后将堆的最后一个元素与堆顶元素进行交换后堆的最后一个元素即为最小记录接着讲前(n-1)个元素重新调整为一个小顶堆再将堆顶元素与当前堆的最后一个元素进行交换后得到次小的记录重复该过程直到调整的堆中只剩一个元素时为止该元素即为最大记录此时可得到一个有序序列。 public class MinHeapSort { public static void adjustMinHeap(int[] a, int pos, int len) { int temp; int child; for (temp a[pos]; 2 * pos 1 len; pos child) { child 2 * pos 1; if (child len a[child] a[child 1]) child; if (a[child] temp) a[pos] a[child]; else break; } a[pos] temp; } public static void myMinHeapSort(int[] array) { int i; int len array.length; for (i len / 2 - 1; i 0; i--) { adjustMinHeap(array, i, len - 1); } for (i len - 1; i 0; i--) { int tmp array[0]; array[0] array[i]; array[i] tmp; adjustMinHeap(array, 0, i - 1); } } int[] a { 5, 4, 9, 8, 7, 6, 0, 1, 3, 2 }; myMinHeapSort(a); } } } 为了让学习变得轻松、高效今天给大家免费分享一套Java教学资源。帮助大家在成为Java架构师的道路上披荆斩棘。需要资料的欢迎加入学习交流群928505736
