2019獨(dú)角獸企業(yè)重金招聘Python工程師標(biāo)準(zhǔn)>>>

這里總結(jié)下各種排序算法的java實(shí)現(xiàn)

冒泡排序

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

public class BubbleSort {? ??????? ???? public static int [] bubbleSort( int [] array) {? ???????? if (array == null ) {? ???????????? return null ;? ???????? }? ??????????? ???????? for ( int i = 0 ; i < array.length; i++) {? ???????????? for ( int j = i + 1 ; j < array.length; j++) {? ???????????????? if (array[i] > array[j]) {? ???????????????????? array[i] = array[i] + array[j];? ???????????????????? array[j] = array[i] - array[j];? ???????????????????? array[i] = array[i] - array[j];? ???????????????? }? ???????????? }? ???????? }? ??????????? ???????? return array;? ???? }? }

插入排序

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

public class InsertSort {? ??? ???? public static int [] insertSort( int [] array) {? ???????? if (array == null ) {? ???????????? return null ;? ???????? }? ??????????? ???????? for ( int i = 1 ; i < array.length; i++) {? ???????????? for ( int j = i; (j > 0 ) && (array[j] < array[j - 1 ]); j--) {? ???????????????? SortUtils.swap(array, j, j - 1 );? ???????????? }? ???????? }? ??????????? ???????? return array;? ???? }? }

選擇排序

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

public class SelectionSort {? ??? ???? public static int [] selectionSort( int [] array) {? ???????? if (array == null ) {? ???????????? return null ;? ???????? }? ??????????? ???????? for ( int i = 0 ; i < array.length; i++) {? ???????????? int lowIndex = i;? ???????????? for ( int j = array.length - 1 ; j > i; j--) {? ???????????????? if (array[j] < array[lowIndex]) {? ???????????????????? lowIndex = j;? ???????????????? }? ???????????? }? ??? ???????????? SortUtils.swap(array, i, lowIndex);? ???????? }? ??????????? ???????? return array;? ???? }? }

Shell排序

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

public class ShellSort {? ??? ???? public static int [] shellSort( int [] array) {? ???????? if (array == null ) {? ???????????? return null ;? ???????? }? ??????????? ???????? for ( int i = array.length / 2 ; i > 2 ; i /= 2 ) {? ???????????? for ( int j = 0 ; j < i; j++) {? ???????????????? insertSort(array, j, i);? ???????????? }? ???????? }? ??? ???????? insertSort(array, 0 , 1 );? ??????????? ???????? return array;? ???? }? ??? ???? private static void insertSort( int [] array, int start, int inc) {? ???????? for ( int i = start + inc; i < array.length; i += inc) {? ???????????? for ( int j = i; (j >= inc) && (array[j] < array[j - inc]); j -= inc) {? ???????????????? SortUtils.swap(array, j, j - inc);? ???????????? }? ???????? }? ???? }? ??? }

快速排序

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

public class QKSort {? ??? ???? public static int [] quickSort( int [] array) {? ???????? if (array != null ) {? ???????????? return quickSort(array, 0 , array.length - 1 );? ???????? }? ??????????? ???????? return null ;? ???? }? ??? ???? private static int [] quickSort( int [] array, int beg, int end) {? ???????? if (beg >= end || array == null ) {? ???????????? return null ;? ???????? }? ??????????? ???????? int p = partition(array, beg, end);? ???????? quickSort(array, beg, p - 1 );? ???????? quickSort(array, p + 1 , end);? ??????????? ???????? return array;? ???? }? ??? ???? /** ????? * 找到分界點(diǎn) ????? * @param array ????? * @param beg ????? * @param end ????? * @return ????? */? ???? private static int partition( int [] array, int beg, int end) {? ???????? int last = array[end];? ???????? int i = beg - 1 ;? ??????????? ???????? for ( int j = beg; j <= end - 1 ; j++) {? ???????????? if (array[j] <= last) {? ???????????????? i++;? ???????????????? if (i != j) {? ???????????????????? array[i] = array[i] ^ array[j];? ???????????????????? array[j] = array[i] ^ array[j];? ???????????????????? array[i] = array[i] ^ array[j];? ???????????????? }? ???????????? }? ???????? }? ??????????? ???????? if ((i + 1 ) != end) {? ???????????? array[i + 1 ] = array[i + 1 ] ^ array[end];? ???????????? array[end] = array[i + 1 ] ^ array[end];? ???????????? array[i + 1 ] = array[i + 1 ] ^ array[end];? ???????? }? ??????????? ???????? return i + 1 ;? ???? }? ??? }

堆排序

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73

public class HeapSort {? ??? ???? public static int [] heapSort( int [] array) {? ???????? if (array == null ) {? ???????????? return null ;? ???????? }? ???????? MaxHeap h = new MaxHeap();? ???????? h.init(array);? ??????????? ???????? for ( int i = 0 ; i < array.length; i++) {? ???????????? h.remove();? ???????? }? ??????????? ???????? System.arraycopy(h.queue, 1 , array, 0 , array.length);? ??????????? ???????? return array;? ???? }? ??? ???? private static class MaxHeap {? ??? ???????? void init( int [] data) {? ???????????? this .queue = new int [data.length + 1 ];? ???????????? for ( int i = 0 ; i < data.length; i++) {? ???????????????? queue[++size] = data[i];? ???????????????? fixUp(size);? ???????????? }? ???????? }? ??? ???????? private int size = 0 ;? ??? ???????? private int [] queue;? ??? ???????? public int get() {? ???????????? return queue[ 1 ];? ???????? }? ??? ???????? public void remove() {? ???????????? SortUtils.swap(queue, 1 , size--);? ???????????? fixDown( 1 );? ???????? }? ??? ???????? // fixdown? ???????? private void fixDown( int k) {? ???????????? int j;? ???????????? while ((j = k << 1 ) <= size) {? ???????????????? if (j < size && queue[j] < queue[j + 1 ]) {? ???????????????????? j++;? ???????????????? }? ??????????????????? ???????????????? // 不用交換? ???????????????? if (queue[k] > queue[j]) {? ???????????????????? break ;? ???????????????? }? ??????????????????? ???????????????? SortUtils.swap(queue, j, k);? ???????????????? k = j;? ???????????? }? ???????? }? ??? ???????? private void fixUp( int k) {? ???????????? while (k > 1 ) {? ???????????????? int j = k >> 1 ;? ???????????????? if (queue[j] > queue[k]) {? ???????????????????? break ;? ???????????????? }? ??????????????????? ???????????????? SortUtils.swap(queue, j, k);? ???????????????? k = j;? ???????????? }? ???????? }? ??? ???? }? }

歸并排序

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

public class MergeSort {? ??? ???? public static int [] mergeSort( int [] array) {? ???????? if (array == null ) {? ???????????? return null ;? ???????? }? ??????????? ???????? int [] temp = new int [array.length];? ???????? return mergeSort(array, temp, 0 , array.length - 1 );? ???? }? ??? ???? private static int [] mergeSort( int [] array, int [] temp, int l, int r) {? ???????? int mid = (l + r) / 2 ;? ???????? if (l == r) {? ???????????? return null ;? ???????? }? ???????? mergeSort(array, temp, l, mid);? ???????? mergeSort(array, temp, mid + 1 , r);? ???????? for ( int i = l; i <= r; i++) {? ???????????? temp[i] = array[i];? ???????? }? ???????? int i1 = l;? ???????? int i2 = mid + 1 ;? ???????? for ( int cur = l; cur <= r; cur++) {? ???????????? if (i1 == mid + 1 ) {? ???????????????? array[cur] = temp[i2++];? ???????????? } else if (i2 > r) {? ???????????????? array[cur] = temp[i1++];? ???????????? } else if (temp[i1] < temp[i2]) {? ???????????????? array[cur] = temp[i1++];? ???????????? } else {? ???????????????? array[cur] = temp[i2++];? ???????????? }? ???????? }? ??????????? ???????? return array;? ???? }? }

歸并排序(改進(jìn))

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

public class MergeSortImproved {? ??? ???? private static final int THRESHOLD = 10 ;? ??? ???? public static int [] mergeSort( int [] array) {? ???????? if (array == null ) {? ???????????? return null ;? ???????? }? ??????????? ???????? int [] temp = new int [array.length];? ???????? return mergeSort(array, temp, 0 , array.length - 1 );? ???? }? ??? ???? private static int [] mergeSort( int [] array, int [] temp, int l, int r) {? ???????? int i, j, k;? ???????? int mid = (l + r) / 2 ;? ???????? if (l == r) {? ???????????? return null ;? ???????? }? ??????????? ???????? if ((mid - l) >= THRESHOLD) {? ???????????? mergeSort(array, temp, l, mid);? ???????? } else {? ???????????? insertSort(array, l, mid - l + 1 );? ???????? }? ??????????? ???????? if ((r - mid) > THRESHOLD) {? ???????????? mergeSort(array, temp, mid + 1 , r);? ???????? } else {? ???????????? insertSort(array, mid + 1 , r - mid);? ???????? }? ??? ???????? for (i = l; i <= mid; i++) {? ???????????? temp[i] = array[i];? ???????? }? ???????? for (j = 1 ; j <= r - mid; j++) {? ???????????? temp[r - j + 1 ] = array[j + mid];? ???????? }? ???????? int a = temp[l];? ???????? int b = temp[r];? ???????? for (i = l, j = r, k = l; k <= r; k++) {? ???????????? if (a < b) {? ???????????????? array[k] = temp[i++];? ???????????????? a = temp[i];? ???????????? } else {? ???????????????? array[k] = temp[j--];? ???????????????? b = temp[j];? ???????????? }? ???????? }? ??????????? ???????? return array;? ???? }? ??? ???? private static void insertSort( int [] array, int start, int len) {? ???????? for ( int i = start + 1 ; i < start + len; i++) {? ???????????? for ( int j = i; (j > start) && array[j] < array[j - 1 ]; j--) {? ???????????????? SortUtils.swap(array, j, j - 1 );? ???????????? }? ???????? }? ???? }? }

轉(zhuǎn)載于:https://my.oschina.net/zhanghaiyang/blog/606275

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的Java基础学习总结（28）——Java对各种排序算法的实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。