欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

八大排序算法(java语言实现编写)

程序员文章站 2022-05-24 18:46:05
冒泡排序、插入排序、希尔排序、快速排序、归并排序、选择排序、堆排序...



冒泡排序

 public static void popSort(int[] array) { for (int i = 0; i < array.length; i++) { for (int j = 0; j < array.length-i-1; j++) {//每次遍历都会使一个最大的数归位 if (array[j] > array[j + 1]) { swap(array, j, j + 1); } } } } /**
    * 交换数组array中下标为j、i的元素
    * @param array
    * @param j
    * @param i
    */ private static void swap(int[] array, int j, int i) { int tmp = array[j]; array[j] = array[i]; array[i] = tmp; } 

冒泡排序核心思想就是每次将两个相邻元素对比,并且把较大的元素放在后面。如此一来每次遍历都会使一个最大的元素到达其排序完成后的位置,比如第一次遍历时就会将最大的一个元素放到最后一个位置。那么只要遍历N(数组元素数量)遍就会使得所有元素均到达其应该在的位置。在第二层循环是这样写的for (int j = 0; j < array.length-i-1; j++)之所以要使array.length-i也就是这个原因,之后的元素已经是排好序的了,所以并不需要继续遍历下去,当然即使不减去i也可以正常完成排序。因为遍历它们也不会对结果造成影响。时间复杂度就是O(n)*O(n)=O(n^2)。从上面的代码也可以看出冒泡排序是稳定的,相同元素在排序过程中并不会改变相对位置。无论是对有序还是无序的数组,遍历次数都是一样的,只是有序数组不会进行交换操作,对时间复杂度无影响。

插入排序

public static void insertSort(int[] array) { for (int i = 1; i < array.length; i++) { int tmp = array[i]; int j = i; while (j > 0 && array[j - 1] > tmp) {//将大于tmp的数往后移 array[j] = array[j - 1]; j--; } array[j] = tmp;//插入 } } 

插入排序也叫直接插入排序,核心思想是假设在第i个数字之前的数组元素是有序的。那么只需要从第i个元素向前遍历将比第i个数字大的元素往后移,碰到比i小的元素就插入进去即可。

希尔排序

希尔排序就是直接插入排序的改进版,也属于一种插入排序。改进的地方在与,每次遍历设置一个步长然后进行直接插入排序,完成一次遍历就将步长减半,直到步长小于等于1。由于每次移动都会移动一个步长的距离,而直接插入排序每次移动只移动一步,所以希尔排序的效率是要比直接插入排序的效率要高的。
八大排序算法(java语言实现编写)

 public static void shellSort(int[] array) { int step = array.length; while (true) { step /= 2; for (int i = 0; i < step; i++) { for (int j = i + step; j < array.length; j += step) { int tmp = array[j]; int k = j; while (k >=step && array[k - step] > tmp) {//将大于tmp的数往后移 array[k] = array[k - step]; k-=step; } array[k] = tmp;//插入 } } if (step <= 1) return; } } 

快速排序

 public static void fastSort(int[] array) { if (array == null) throw new NullPointerException(); fastSortHelp(array, 0, array.length - 1); } private static void fastSortHelp(int[] array, int left, int right) { if (right > left) { int index = getIndex(array, left, right); fastSortHelp(array, left, index - 1); fastSortHelp(array, index + 1, right); } } private static int getIndex(int[] array, int left, int right) { int tmp = array[left]; while (left < right) { while (left < right && array[right] > tmp) {//找到第一个比tmp小的数 right--; } if (left < right) { array[left] = array[right]; left++; } while (left < right && array[left] < tmp) { left++; } if (left < right) { array[right] = array[left]; right--; } } array[left] = tmp; return left; } 

快速排序是一个常用的排序算法,当数组顺序越混乱它的效率越高。用来求数组的第k大的元素也非常好用。getIndex(int[] array, int left, int right)这一个方法是核心,它将所有大于array[left]的元素放在右边,小于它的放在左边,那么就得到了array[left]排序完成后的坐标,然后对它的左右子数组分别递归调用快速排序,即可完成排序。也正是由于这个方法的特性,每次调用getIndex()方法就会使得一个元素回到它应该在的位置。所以这个方法返回的下标k就是第k大或者第k小的元素。

归并排序

归并排序是一个非原地排序算法,他需要用额外O(n)的空间来储存排序完成后的数组,然后返回这一个排好序的数组,对原数组并不会改动。这一特性可用于一些不希望改变原数组的情况,且免于对原数组进行拷贝。核心思想就是’分而治之’,每次将数组分为左右两半,然后对这两个子数组继续递归调用,直到不能分割,然后在回溯过程中将左右数组合并。合并过程就是排序过程,申请一个足够容纳左右子数组所有元素的新数组,然后每次取出左右数组中较小/较大的元素,放入新的数组,以此保证新数组有序。然后将这个新的数组返回,完成排序。

 public static int[] mergeSort(int[] array) { if (array == null) throw new NullPointerException(); array = mergeSortHelp(array, 0, array.length - 1); return array; } private static int[] mergeSortHelp(int[] array, int start, int end) { if (start == end) return new int[]{array[start]}; else { int mid = (end + start) / 2; int[] leftArray = mergeSortHelp(array, start, mid); int[] rightArray = mergeSortHelp(array, mid + 1, end); return mergeArray(leftArray, rightArray); } } private static int[] mergeArray(int[] leftArray, int[] rightArray) { int[] newArray = new int[leftArray.length + rightArray.length]; int nIndex = 0, lIndex = 0, rIndex = 0; while (lIndex < leftArray.length && rIndex < rightArray.length) {//每次取出一个较大的数复制到新数组 newArray[nIndex++] = leftArray[lIndex] > rightArray[rIndex] ? rightArray[rIndex++] : leftArray[lIndex++]; } while (lIndex < leftArray.length) { newArray[nIndex++] = leftArray[lIndex++]; } while (rIndex < rightArray.length) newArray[nIndex++] = rightArray[rIndex++]; return newArray; } 

选择排序

 public static void selectSort(int[] array) { //每次选择最小元素,放在第一个位置 for (int i = 0; i < array.length; i++) { int minIndex = i; for (int j = i + 1; j < array.length; j++) {//获得最小元素下标 if (array[j] < array[minIndex]) minIndex = j; } swap(array,i,minIndex); } } 

也叫简单选择排序,这名字也确实符合它的特点。这个算法很简单,第i次遍历从数组后length-i个元素里找到最小的元素,然后将它放在第i个。就相当于与有两个数组,每次从没有排序的数组里移除一个最小的元素,放到排好序的数组里,直到没有排序的数组元素都被移除。

堆排序

堆排序也是一种选择排序,同样是每次遍历拿出一个最大/最小的数字放到数组尾部(这么说并不准确,应该说是放到已排序数组的头部,只不过我们在原地排序,这个已排序数组我们将其放在原始数组的尾部,所以叫它尾部)然后继续对数组进行同样的操作,直到所有数字均被取出。与简单选择排序不同的是,我们维护一个堆,每次堆顶元素都是未排序数组的最大值。这样取出最大元素的操作就不必每次遍历所有未排序元素了。

public static void heapSort(int[] array) { //把数组当成满二叉树 //i结点的左孩子下标为i*2+1. for (int i = array.length / 2 - 1; i >= 0; i--) {//构建大顶堆 siftDown(array, i, array.length); } for (int i = array.length - 1; i >= 0; i--) {//将堆顶元素放置最后(堆大小-1),然后重新构建大顶堆 swap(array, 0, i); siftDown(array, 0, i); } } private static void siftDown(int[] array, int i, int length) { int key = array[i]; int half = length >>> 1; while (i < half) { int child = (i << 1) + 1; if (child + 1 < length && array[child] < array[child + 1]) { child++; } if (array[child] <= key) { break; } array[i] = array[child]; i = child; } array[i] = key; } 

siftDown(int[] array, int i, int length)是一个下沉操作,它将第i个元素下沉。那么何种情况会下沉呢?当子节点比它大时就下沉,将较大的元素上浮。这样可以保证对于堆中的任意一个节点,它的所有子孙节点都比它小。Java中的PriorityQueue就是采用的这种方式维护大顶堆/小顶堆。下面是PriorityQueue中的一段源码:

 private static <T> void siftDownComparable(int k, T x, Object[] es, int n) { // assert n > 0; Comparable<? super T> key = (Comparable<? super T>)x; int half = n >>> 1; // loop while a non-leaf while (k < half) { int child = (k << 1) + 1; // assume left child is least Object c = es[child]; int right = child + 1; if (right < n && ((Comparable<? super T>) c).compareTo((T) es[right]) > 0) c = es[child = right]; if (key.compareTo((T) c) <= 0) break; es[k] = c; k = child; } es[k] = key; } 

基数排序/桶排序

…那个本人也还没有掌握这种算法,手撕不出来。且容我学习一会再更…

本文地址:https://blog.csdn.net/First_C0de/article/details/107958580