Java排序算法

各种内部排序算法的比较

冒泡排序

冒泡排序:一种交换排序,它的基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。稳定排序算法

时间复杂度 O(n2),里层循环每趟比较第 j 项和第 j+1项,如果前项大于后项,则发生交换。缺点是每次比较后都可能发生交换,交换次数太多了,值从小到大。

通俗概述:依次比较相邻两关键字,如果反序则立即发生交换,如果正序则继续比较下一个相邻项,双重嵌套循环实现

具体如何移动呢?我们先看一个例子

有8个数字组成一个无序数列{5,6,3,1,8,7,2,4},希望按照从小到大的顺序 对其进行排序。详细排序如下,第一轮排序结束,最大元素8冒泡排到最后。以此类推,下一轮7排序到倒数第二的位置…

实现代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class BubbleSort {
// 利用双重循环,如果前一个数比后一个数大,则发生交换,每次比较都发生交换
public static void sort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 1; j < arr.length - i; j++) {
if (arr[j-1] > arr[j]) {
swap(arr, j-1, j);
}
}
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr=new int[]{5,6,3,1,8,7,2,4};
sort(arr);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7, 8]
}
}

选择排序

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

代码实现

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
public class SelectionSort {

public static void sort(int array[]){
for (int i = 0; i < array.length; i++) {
int minIndex = i; // 用来保存最小的索引,初始指向当前第i项
for (int j = i; j < array.length; j++) {
// 找到最小的数
if (array[j] < array[minIndex]) {
//将最小数的索引保存
minIndex = j;
}
}
// 交换元素。最小元素排在前边,依次递增
int temp = array[minIndex];
array[minIndex] = array[i];
array[i] = temp;
}
}

public static void main(String[] args) {
int[] arr=new int[]{5,6,3,1,8,7,2,4};
sort(arr);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7, 8]
}
}

插入排序

插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。就像打扑克整理牌一样。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class InsertionSort {

public static void sort(int[] arr) {
// 第一个肯定是有序的,所以从第二个数开始遍历
for (int i=1; i<arr.length; i++) {
int current = arr[i]; // 取出第i个数,和前i-1个数比较,插入合适位置。
int preIndex = i - 1; // 前一个数索引
// 当发现小元素时,将已排序元素中所有大于它的后移一个单位
while(preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
// 将目标元素插入到位移后留下的空位。最后一次交换结束后再自减运算,所以这里需要+1
arr[preIndex + 1] = current;
}
}

public static void main(String[] args) {
int[] arr=new int[]{5,6,3,1,8,7,2,4};
sort(arr);
System.out.println(Arrays.toString(arr));
}
}

快速排序

快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

代码实现

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
public class QuickSort {

public static void sort(int[] arr, int startIndex, int endIndex) {
// 递归结束条件: startIndex大于等于endIndex
if (startIndex >= endIndex) {
return;
}
//得到基准元素位置
int pivotIndex = partition(arr, startIndex, endIndex);
// 根据基准元素,分成2部分进行递归排序
sort(arr, startIndex, pivotIndex-1);
sort(arr, pivotIndex+1, endIndex);
}

// 分治(双边循环法)
public static int partition(int[] arr, int startIndex, int endIndex) {
// 取第一个位置的元素作为基准元素
int pivot = arr[startIndex];
int left = startIndex;
int right = endIndex;

while (left != right) {
// 控制right指针比较并左移,找到第一个小于基准值的元素索引
while (left < right && arr[right] > pivot) {
right--;
}
// 控制left指针比较并右移, 找到第一个大于基准值的元素索引
while (left < right && arr[left] <= pivot) {
left++;
}
// 交换left和right指针所指向的元素
if (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}

// pivot和指针重合点交换
arr[startIndex] = arr[left];
arr[left] = pivot;

return left;
}

public static void main(String[] args) {
int[] arr=new int[]{5,6,3,1,8,7,2,4};
sort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7, 8]
}
}

总结快速排序的思想:冒泡+二分+递归分治

希尔排序

希尔排序:又称为增量排序,它是一种插入排序,它是直接插入排序算法的一种威力加强版。它的基本思想是:把记录按步长 gap(差距,间隙) 分组,对每组记录采用直接插入排序方法进行排序。 随着步长逐渐减小,所分成的组包含的记录越来越多,当步长的值减小到 1 时,整个数据合成为一组,构成一组有序记录,则完成排序。

时间复杂度为O(nlogn),该方法因DL.Shell于1959年提出而得名。超越了O(n2)的算法的历史。他是在直接插入排序的增强,将记录按步长gap分组,然后在分组内进行直接插入排序。不稳定算法。

代码实现

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
public class ShellSort {

public static void sort(int[] arr) {
//初始化步长为数组长度的一半
int gap = arr.length / 2;
//循环结束条件,当gap<1是,循环结束,即排序结束
while (gap >= 1) {
//把距离为gap的元素编为一个组,扫描所有组
for (int i = gap; i < arr.length; i++) {
int current = arr[i];//保存待插入元素,以便组内元素向后移动覆盖
int j = i;
//对距离为gap的组内元素进行直接选择排序
while (j-gap >=0 && current < arr[j-gap]) {
arr[j] = arr[j-gap];
j-=gap;
}
//将待插入元素插入合适位置
arr[j] = current;
}
//一次循环结束,所有分组均已完成直接选择排序,则可将将距离缩小为原本的一半
gap/=2;
}
}

public static void main(String[] args) {
int[] arr=new int[]{5,6,3,1,8,7,2,4};
sort(arr);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7, 8]
}
}

堆排序

堆排序:就是利用堆进行排序的方法。它的基本思想是,将待排序的序列构造成一个大顶堆。此时,整个序列的最大值就是堆顶的根结点,将它移走(其实就是将其与堆数组的末尾元素交换,此时末尾元素就是最大值),然后将剩余的n-1给序列重新构造成一个堆,这样就会得到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
public class HeapSort {

/**
* 将数组调整为符合堆规律的结构
* @param arr 传入需要调整的数组
* @param parent 父结点
* @param length 需要调整的数组长度
*/
public static void heapAdjust(int[] arr, int parent, int length) {
int temp = arr[parent];//先保存父结点的值,以便后续移动交换
int child = parent * 2 + 1;//先获取到该父结点的左子结点
while (child < length) {
//如果存在右子结点,且右子结点大于左子结点,则选取右子结点
if (child + 1 < length && arr[child] < arr[child + 1]) {
child++;
}
//判断父结点(待插入的值)是否比子节点大
if(temp>arr[child]){
break;//父结点大,结束当前循环
}else {
/*此处类似与直接插入排序的思想*/
arr[parent]=arr[child];//将子结点的值覆盖父节点的值
parent=child;
child=child *2+1;
}
}
//此时已经找到合适的位置,将待插入的值插入合适的位置
arr[parent]=temp;
}

/**
*堆排序(升序)
* @param list
*/
public static void sort(int[] list){
// 把无序数组构建成最大堆
for (int i = list.length/2; i >=0 ; i--) {
heapAdjust(list,i,list.length);
}
//循环删除堆顶元素
for (int i = list.length-1; i >0; i--) {
//将最大值list[0]与最后一个元素交换
int temp=list[i];
list[i]=list[0];
list[0]=temp;
//交换完之后,最大值已经在底层数组的末尾,然后将交换后的堆进行调整
heapAdjust(list,0,i);//注意这里的长度已经-1了,所以堆调整不包含最后一个元素
}
}

public static void main(String[] args) {
int[] arr=new int[]{5,6,3,1,8,7,2,4};
sort(arr);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7, 8]
}
}

归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

代码实现

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
public class MergeSort {

/**
* 递归分治
* @param arr
* @param left
* @param right
*/
public static void sort(int[] arr, int left, int right) {
if(left >= right)
return ;
int mid = (left + right) / 2;

sort(arr, left, mid); //递归排序左边
sort(arr, mid+1, right); //递归排序右边
merge(arr, left, mid, right); //合并
}

/**
* 合并两个有序数组
* @param arr 待合并数组
* @param left 左指针
* @param mid 中间指针
* @param right 右指针
*/
public static void merge(int[] arr, int left, int mid, int right) {
//[left, mid] [mid+1, right]
int[] temp = new int[right - left + 1]; //中间数组

int i = left;
int j = mid + 1;
int k = 0;
while(i <= mid && j <= right) {
if(arr[i] <= arr[j]) {
temp[k++] = arr[i++];
}
else {
temp[k++] = arr[j++];
}
}

while(i <= mid) {
temp[k++] = arr[i++];
}

while(j <= right) {
temp[k++] = arr[j++];
}

for(int p=0; p<temp.length; p++) {
arr[left + p] = temp[p];
}
}

public static void main(String[] args) {
int[] arr=new int[]{5,6,3,1,8,7,2,4};
sort(arr,0, arr.length-1);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7, 8]
}
}

计数排序

计数排序不是基于比较的排序算法,其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。

算法描述

  • 找出待排序的数组中最大和最小的元素;
  • 统计数组中每个值为i的元素出现的次数,存入数组C的第i项;
  • 对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加);
  • 反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(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
public class CountingSort {

public static void sort(int[] arr) {
//找出数组中的最大值
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
//初始化计数数组
int[] countArr = new int[max + 1];
Arrays.fill(countArr, 0);

//计数
for (int i = 0; i < arr.length; i++) {
countArr[arr[i]]++;
}

//排序
int index = 0;
for (int i = 0; i < countArr.length; i++) {
for(int j=0; j< countArr[i]; j++) {
arr[index++] = i;
}
}
}

public static void main(String[] args) {
int[] arr=new int[]{5,6,3,1,8,7,2,4};
sort(arr);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7, 8]
}
}

桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排)。

算法描述

  • 设置一个定量的数组当作空桶;
  • 遍历输入数据,并且把数据一个一个放到对应的桶里去;
  • 对每个不是空的桶进行排序;
  • 从不是空的桶里把排好序的数据拼接起来。

代码实现

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
public class BucketSort {
public static void sort(int[] arr){
//最大最小值
int max = arr[0];
int min = arr[0];
int length = arr.length;

for(int i=1; i<length; i++) {
if(arr[i] > max) {
max = arr[i];
} else if(arr[i] < min) {
min = arr[i];
}
}

//最大值和最小值的差
int diff = max - min;

//桶列表
ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();
for(int i = 0; i < length; i++){
bucketList.add(new ArrayList<>());
}

//每个桶的存数区间
float section = (float) diff / (float) (length - 1);

//数据入桶
for(int i = 0; i < length; i++){
//当前数除以区间得出存放桶的位置 减1后得出桶的下标
int num = (int) (arr[i] / section) - 1;
if(num < 0){
num = 0;
}
bucketList.get(num).add(arr[i]);
}

//桶内排序
for(int i = 0; i < bucketList.size(); i++){
//jdk的排序速度当然信得过
Collections.sort(bucketList.get(i));
}

//写入原数组
int index = 0;
for(ArrayList<Integer> arrayList : bucketList){
for(int value : arrayList){
arr[index] = value;
index++;
}
}
}

public static void main(String[] args) {
int[] arr=new int[]{5,6,3,1,8,7,2,4};
sort(arr);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7, 8]
}
}

基数排序

基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。

算法描述

  • 取得数组中的最大数,并取得位数;
  • arr为原始数组,从最低位开始取每个位组成radix数组;
  • 对radix进行计数排序(利用计数排序适用于小范围数的特点);

代码实现

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
public class RadixSort {
public static void sort(int[] arr){
int length = arr.length;

//最大值
int max = arr[0];
for(int i = 0;i < length;i++){
if(arr[i] > max){
max = arr[i];
}
}
//当前排序位置
int location = 1;

//桶列表
ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();

//长度为10 装入余数0-9的数据
for(int i = 0; i < 10; i++){
bucketList.add(new ArrayList());
}

while(true)
{
//判断是否排完
int dd = (int)Math.pow(10, (location - 1));
if(max < dd){
break;
}

//数据入桶
for(int i = 0; i < length; i++)
{
//计算余数 放入相应的桶
int number = ((arr[i] / dd) % 10);
bucketList.get(number).add(arr[i]);
}

//写回数组
int nn = 0;
for (int i=0;i<10;i++){
int size = bucketList.get(i).size();
for(int ii = 0;ii < size;ii ++){
arr[nn++] = bucketList.get(i).get(ii);
}
bucketList.get(i).clear();
}
location++;
}
}

public static void main(String[] args) {
int[] arr=new int[]{5,6,3,1,8,7,2,4};
sort(arr);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7, 8]
}

}