记录生活中的点点滴滴

0%

排序

排序

排序这东西可太重要了,去年学数据结构就晓得有那么多排序了,现在好像连冒泡和选择都还没彻底搞明白。

这篇文章的主要内容:

  • 冒泡排序
  • 选择排序
  • 插入排序
  • 希尔排序
  • 归并排序
  • 快速排序
  • 堆排序

还有一些排序,比如基数排序和桶排序,代码还没写过,感觉好像挺恶心的,先不管了。

冒泡排序

冒泡排序的英语名是Bubble Sort,是一种最基础的交换排序。

说白了,就是两层循环,外面一层从0到len-1,里面一层从0到 len-i-1,内层for里面进行j与j+1的比较。

这样内层for循环结束之后,最大的值就会冒泡到最右边,以此类推……

1
2
3
4
5
6
7
8
9
10
11
public static void sort(int[] arr){
for (int i = 0; i < arr.length-1; i++) {
for (int j = 0; j < arr.length-1-i; j++) {
if(arr[j]>arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}

冒泡优化:冒泡有一个最大的问题就是这种算法不管不管你有序还是没序,闭着眼睛把你循环比较了再说。有时候本来就是一个有序的或者冒泡几次就已经有序了,没必要在进行循环了。针对这个问题,我们可以设定一个临时遍历来标记该数组是否已经有序,如果有序了就不用遍历了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//冒泡优化
public static void sortImprove(int[] arr){
for (int i = 0; i < arr.length-1; i++) {
boolean isSorted = true;
for (int j = 0; j < arr.length-1-i; j++) {
if(arr[j]>arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
isSorted = false;
}
}
if(isSorted)
break;
}
}

选择排序

首先,找到数组中最小的元素,拎出来,将它和数组的第一个元素交换位置,第二步,在剩下的元素中继续寻找最小的元素,拎出来,和数组的第二个元素交换位置,如此循环,直到整个数组排序完成。

1
2
3
4
5
6
7
8
9
10
11
12
public static void sort(int[] arr){
for (int i = 0; i < arr.length; i++) {
int min = i;
for (int j = i+1; j < arr.length; j++) {
if(arr[j]<arr[min])
min = j;
}
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}

插入排序

插入排序的思想和我们打扑克摸牌的时候一样,从牌堆里一张一张摸起来的牌都是乱序的,我们会把摸起来的牌插入到左手中合适的位置,让左手中的牌时刻保持一个有序的状态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void sort(int[] arr){
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
int j;
for (j = i-1; j >= 0; j--) {
if(arr[j]>temp){
arr[j+1] = arr[j];
}else {
break;
}
}
arr[j+1] = temp;
}
}

希尔排序

插入排序在小规模数据或者基本有序时十分高效,怎么对插入排序进行改进,是的它对较大规模并且无序的数据也非常有效率,希尔排序就可以实现它。

  • 首先它把较大的数据集合分割成若干个小组(逻辑上分组),然后对每一个小组分别进行插入排序,此时,插入排序所作用的数据量比较小(每一个小组),插入的效率比较高。

  • 每个分组进行插入排序后,各个分组就变成了有序的了(整体不一定有序)

  • 然后缩小增量为上个增量的一半;继续划分分组,此时,每个分组元素个数多了,但是,数组变的部分有序了,插入排序效率同样比高

  • 同理对每个分组进行排序(插入排序),使其每个分组各自有序

  • 依次类推,则整个数组被分为一组,此时,整个数组已经接近有序了,插入排序效率高,对这仅有的一组数据进行排序,排序完成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void sort(int[] arr){
int len = arr.length;
int gap = len/2;//间隔从长度的一半开始
while (gap>0){
//前面gap个其实就是每个数组的第一位,然后每个数组从后面进行插入排序
for (int i = gap; i < len; i++) {
//这里面其实就是插入排序
int temp = arr[i];
int j = i-gap;
while (j>=0 && temp<arr[j]){
arr[j+gap] = arr[j];
j-=gap;
}
arr[j+gap] = temp;
}
gap/=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
public class MergeSort {
public static void main(String[] args) {
int[] arr = new int[]{5,1,6,3,7,2,4,8};
int[] tempArr = new int[arr.length];
sort(arr,tempArr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
//归并排序
public static void sort(int[] arr,int[] tempArr,int start,int end){
if(start>=end)//先判断
return;
//使用分治递归
int middle = start + (end-start)/2;
sort(arr,tempArr,start,middle);
sort(arr,tempArr,middle+1,end);
merge(arr,tempArr,start,middle,end);
}
//把两个有序数组合并
public static void merge(int[] arr,int[] tempArr,int start,int middle,int end){
for (int i = start; i <= end; i++)
tempArr[i] = arr[i];
int k = start;
int left = start;//左边首位下标
int right = middle+1;//右边首位下标
//合并两个有序数组
while (left<=middle && right<=end){
arr[k++] = tempArr[left]<tempArr[right] ? tempArr[left++] : tempArr[right++];
}
while (left<=middle)
arr[k++] = tempArr[left++];
while (right<=end)
arr[k++] = tempArr[right++];
}
}

快速排序

快速排序的核心思想也是分治法,分而治之。它的实现方式是每次从序列中选出一个基准值,其他数依次和基准值做比较,比基准值大的放右边,比基准值小的放左边,然后再对左边和右边的两组数分别选出一个基准值,进行同样的比较移动,重复步骤,直到最后都变成单个元素,整个数组就成了有序的序列。

是冒泡排序的升级,和冒泡排序一样,都属于交换排序的一种。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class No6QuickSort {
public static void main(String[] args) {
int[] arr = new int[]{5,6,1,2,8,7,4,3};
quickSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr,int left,int right){
if(left >= right)
return;
//切分然后递归
int pivotIndex = partition(arr,left,right);
quickSort(arr,left,pivotIndex-1);
quickSort(arr,pivotIndex+1,right);
}
}

partition 交换方法有两种,一种是单边循环法,一种是双边循环法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**单边循环法
* 思想就是先定义一个基准值为;left,然后遍历,遇到比pivot小的:mark加1,交换arr【i】与arr【mark】
* 这样遍历完成之后,mark以及mark之前的值全部都是比pivot小的,mark之后的值全部都是比pivot大的
* 最后还要交换arr【left】与arr【mark】
*/
public static int partition(int[] arr, int left, int right) {
int pivot = arr[left];//取基准值
int mark = left;//mark初始化为其实下标
//要把pivot前全是比它小的,pivot之后全是比它大的
for (int i = left+1; i <= right; i++) {
if(arr[i]<pivot){
mark++;
int temp = arr[mark];
arr[mark] = arr[i];
arr[i] = temp;
}
}
//交换arr【left】与arr【mark】
arr[left] = arr[mark];
arr[mark] = pivot;
return mark;
}
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 static int partitionV2(int[] arr, int start, int end) {
int pivot = arr[start];
int left = start;
int right = end;
while (left!=right){
while (left<right && arr[right]>pivot)
right--;
while (left<right && arr[left]<=pivot)
left++;
if(left<right){
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
arr[start] = arr[left];
arr[left] = pivot;
return left;
}

堆排序

堆排序顾名思义,是利用堆这种数据结构来进行排序的算法。

堆的特性:

  • 必须是完全二叉树
  • 任一结点的值是其子树所有结点的最大值或最小值

构建二叉堆的过程其实就是让所有非叶子节点依次下沉

二叉堆插入节点就是最后一个位置不断上浮

二叉堆删除头结点就是用最后一个元素代替头结点然后下沉

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
public class No7HeapSort {
public static void main(String[] args) {
int[] arr = new int[]{8,4,1,6,3,7,5,2};
sort(arr);
System.out.println(Arrays.toString(arr));
}

public static void sort(int[] arr) {
int len = arr.length;
//构建堆
buildHeap(arr,len);
//构建堆完成之后,交换arr【0】与arr【len-1】,隐藏arr【len-1】
//将a【0】下沉,主要将最大元素浮上来
for (int i = len-1; i >0 ; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
sink(arr,0,i);
}
}
//构建最大堆,让所有非叶子节点一次下沉
public static void buildHeap(int[] arr, int len) {
for (int i = len/2; i >= 0; i--) {
sink(arr,i,len);
}
}

/***
* 下沉调整
* @param arr 数组
* @param i 调整位置
* @param len 数组范围
*/
public static void sink(int[] arr, int i, int len) {
int parent = i;
int temp = arr[i];//节点值
int child = 2*i+1;//左孩子
while (child<len){//这里的判断条件一定要是这
//这里的判断条件,要考虑没有右孩子节点的情况
if(child+1<len && arr[child+1]>arr[child])//右边大于左边,定位到右边
child++;
if(temp>arr[child])//如果父节点大于左边和右边,则直接跳出
break;
//无序真正交换,直接遍历赋值
arr[parent] = arr[child];
parent = child;
child = 2*child+1;
}
//最后要换回来
arr[parent] = temp;
}
}