八大排序算法JAVA实现（时间复杂度O(n*n)篇）

本文主要描述3个时间复杂度为n²的排序算法：冒泡排序、选择排序、插入排序。

1.冒泡排序：由数组头部开始，一次比较两个元素，如果他们的顺序错误就把他们交换过来。每次交换完成后，当前数组最大值就会被放在最后。

 1     public int[] bubbleSort(int[] a, int n)
 2     {
 3         for (int j = 0; j < n - 2; j++)
 4         {
 5             for (int i = 0; i < n - j - 1; i++)
 6             {// 如果当前数比下一个大，交换，否则继续看下一个数
 7                 if (a[i] > a[i + 1])
 8                 {
 9                     int temp = a[i + 1];
10                     a[i + 1] = a[i];
11                     a[i] = temp;
12                 }
13             }
14         }
15         return a;
16     }
17

传入参数：a为待排序数组，n为数组长度。

第一个for循环，用j的值控制第二个循环，即比对数组的长度。由冒泡排序的定义可知，每一次都会将最大值放在最后，所以下一次排的时候就可以少管一个数；

第二个for循环，将两个数比对，大的放在后面。

本题第一个for循环是一种小小的优化，可以不使用，直接对整个数组进行交换也是没有问题的。

2.选择排序：每次在数组中选择最小的一个数，将其依次放在数组头对应位置。

 1     public int[] selectionSort(int[] a, int n)
 2     {
 3         for (int j = 0; j < n - 1; j++)
 4         {//j表示需要在以j开始的数组里面寻找一个最大值填充j位
 5             int maxi = 0;
 6             for (int i = 0; i < n - j; i++)
 7             {// maxi表示当前序列最大值的下标
 8                 if (a[maxi] < a[i])
 9                 {
10                     maxi = i;
11                 }
12             }
13             if (maxi != n - j - 1)
14             {
15                 int temp = a[n - j - 1];
16                 a[n - j - 1] = a[maxi];
17                 a[maxi] = temp;
18             }
19         }
20         return a;
21     }

3.插入排序：将其模拟为往一个有序数组中插入一个值。关键在于需要把有序数组比当前数大的数字一个个往后移动。

 1     public int[] insertionSort(int[] a, int n)
 2     {
 3         for (int i = 1; i < n; i++)
 4         {//认为a[0]只有一个数，是有序的。所以从第二个数开始插入
 5             int nowNum = a[i];
 6             int j = i - 1;
 7             for (; j >= 0; j--)
 8             {//把所有比插入数大的数字往后挪，循环结束后就会留出一个空位
 9                 if (nowNum < a[j])
10                 {
11                     a[j + 1] = a[j];
12                 }
13                 else
14                 {
15                     break;
16                 }
17             }
18             a[++j] = nowNum;
19         }
20         return a;
21     }

JAVA学习网

分类

八大排序算法JAVA实现（时间复杂度O(n*n)篇）