swaggyW's Blog

感谢来访~~~~~

0%

排序下

发表于 更新于 分类于

快速排序

 快速排序的思想是快速排序，通过首尾两个指针进行扫描

先让val=arr[0]
尾指针先开始移动，如果所指元素大于val， 则指针往前移动，当arr[i] < val的时候， 并且arr[0] = arr[i],尾指针停止移动
首指针开始移动, 当所指元素小于val的时候，指针后移，当arr[i] > val 的时候，让arr[尾指针位置] = arr[i]
终止条件： 尾指针的索引小于或者等于首指针

​ 这样一轮过后，就可以确定该元素在数组中的位置，通过迭代的方法，来将基准数归位。

​ 假设现在有这样一个数组

​ arrsort

​ 取出int val = arr[0] = 3, 首先，尾指针开始移动，直到找到arr[i]=1 < val,这时尾指针停止移动，并且把这个值赋给首指针指向的空间。

​ 01

​ 此时首指针开始移动，当arr[i] > val 的时候，将此时的值赋给尾指针所指向的位置。

02

​ 然后尾指针开始移动，直到low >= high ，则结束，此时首尾指针重合，所指向的位置就是val排序后的位置。

04

大致就是这个过程，然后通过递归的方式，找到数的位置就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pos = findPos(arr, low, high);//找到当前元素的位置
        //将数组分割，进行快排。
        quickSort(arr, low, pos-1);
        quickSort(arr, pos+1, high);
    }
}

public int fingPos(int[] arr, low, high) {
    int val = arr[low]; //保存值，
    while (low < high) {
        while (low < high && arr[high] >= val) high --;
        arr[ow] = arr[high];
        while (low < high && arr[low] <= val) low ++;
        arr[high] = arr[low];
    }
    arr[low] = val;
    return low;
}

快排的时间复杂度为O(nlogn)，并且不稳定。

基数排序

​ 基数排序是通过空间来换时间的排序，需要更多的内存空间。基数排序需要10个一维数组（0123456789）。

​ 首先，取出数组元素中所有元素的个位数，根据个位数字，将数组元素，放入到对应的一维数组中，比如有一个元素是98，其个位数字是8，那么就将98放入到第九个（即编号为8）的数组中。

​ 放完所有元素之后，在按照顺序，从十个二维数组中取出来，组成新的数组，然后在比较十位，如果没有十位数字的元素则为0，然后重复上述操作，按顺序取出来，形成了新的数组。如此反复。

​ 假设有现在一个数组如下

arr

​ 取出个位数字，放入到十个一维数组中，并取出形成新的数组

geweishu

​ 取出十位数字，同样放入再取出，形成新的数组

shiweishuzi

最后取出百位

baiwei

最后形成的数组已经排好了。代码如下：

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
public void radixSort(int[] nums) {
  int[][] buckets = new int[10][nums.length];
  int[] bucketCount = new int[10];
  // get Max Element;
  int max = nums[0];
  for (int i = 1; i < nums.length; i++) {
    if (max < nums[i]) {
      max = nums[i];
    }
  }
  int maxLen = (max + "").length();
  for (int i = 0, n = 1; i < maxLen; i++, n *= 10) {
    for (int j = 0; j < nums.length; j++) {
      int digit = nums[j] / n % 10;
      buckets[digit][bucketCount[digit]++] = nums[j];
    }
    int index = 0;
    for (int k = 0; k < bucketCount.length; k++) {
      if (bucketCount[k] > 0) {
        for (int h = 0; h < bucketCount[k]; h++) {
          nums[index++] = buckets[k][h];
          buckets[k][h] = 0;
        }
      }
      bucketCount[k] = 0;
    }
  }
}

基数排序的时间复杂度为O（logRB），稳定。

归并排序

​ 归并排序，先将数组进行拆分，拆分成一个一个元素，将每个元素当做一个数组。然后在从最底层，进行合并，将两个数组合并成一个新的数组，最后变成有序数组。

先看下面的数组，拆分的过程

merge

然后在进行合并，如下每一个都代表一个数组

merge02

简单来说，就是先对数组进行拆分，拆分到最后每个元素都是一个数组，然后在将数组进行合并，放入一个新的数组中。

代码如下

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
public void mergeSort(int[] nums, int left, int right, int[] tmp) {
  if (left < right) {
    int mid = left + (right - left) / 2;
    mergeSort(nums, left, mid, tmp);
    mergeSort(nums, mid + 1, right, tmp);
    merge(nums, left, mid, right, tmp);
  }
}

private void merge(int[] nums, int left, int mid, int right, int[] tmp) {
  for (int i = left; i <= right; i++) {
    tmp[i] = nums[i];
  }

  int i = left;
  int j = mid + 1;
  for (int k = left; k <= right; k++) {
    if (i == mid + 1) {
      nums[k] = tmp[j];
      j++;
    } else if (j == right + 1) {
      nums[k] = tmp[i];
      i++;
    } else if (tmp[i] <= tmp[j]) {
      nums[k] = tmp[i];
      i++;
    } else {
      nums[k] = tmp[j];
      j++;
    }
  }
}

归并排序算法每次将序列折半分组，共需要logn轮，因此归并排序算法的时间复杂度是O(nlogn)。并且是稳定的。

堆排序

​ 堆排序是将一个无序的数组构建成一个堆，如果升序则构建成大顶堆、降序则构建小顶堆。

​ 大顶堆： 从最后一个非叶子节点开始，该节点的值大于或等于其左右孩子节点的值，小顶堆则相反。

​ 构建好大顶堆之后，将最末尾元素和根节点交换，这样末尾元素就是最大值，然后再重新调整堆，然后在交换根节点与末尾元素。如此反复。

​ 我们举个例子，现在有一个数组如下

heaparr

​ 先构建大顶堆，最后一个非叶子节点arr[1] = 7, 比较左右孩子节点，发现右孩子值最大，则交换位置

heap01

接着找到倒数第二个非叶子节点，arr[0] = 5，左孩子比它大，所以交换位置，如下：

heap02

然后继续调整堆

heap03

最后就得到了一个大顶堆。

得到大顶堆后，根节点为数组最大值，这时，把根节点与最末元素进行交换，则最末元素是最大值。然后再进行调整，按照数组的下标，对于第k个节点，它的左孩子是2k+1、它的右孩子是2k+2。将9和5交换位置，就确定了最大值

heapsort01

然后对剩下的元素，再进行调整，让他成一个大顶堆

heapsort02

再次进行根节点和末尾元素进行交换。即7和1交换

heaosort03

剩下的元素，再进行大顶堆的调整

heapsort

然后再进行交换，即5和3

heapsort05

然后对剩下的元素进行大顶堆调整，最后进行元素交换，得到最终结果

lastsort

堆排序，主要是对大顶堆的构建及调整。然后交换元素，然后再进行调整。

代码如下

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 void heapSort(int[] arr) {
    //先构建一个大顶堆。大顶堆是一颗完全二叉树，最后一个非叶子节点的值一定是arr.length/2 -1
    for (int i=arr.length/2 - 1; i >=0; i--) {
        adjustHeap(arr, i, arr.length)
    }
    
    //然后将最后一个元素与第一个元素进行交换
    for (int j=arr.length-1; j>=0; j--) {
        swap(arr, 0, j);
        adjustHeap(arr, 0, j);
    }
}


//调整大顶堆
/**
*  @Param int[] arr  需要比较的数组
*  @Param i          当前的非叶子节点
*  @Param length     需要调整的数组的长度 
* 
*/
public void adjustHeap(int[] arr, int i, int length) { 
    //先保存当前非叶子节点的值
    int val = arr[i];
    //从当前非叶子节点的左孩子出发，开始遍历
    for (int k = 2*i+1; k<length; k = 2*k+1) {
        //比较两个孩子的大小，如果右孩子的值比左孩子大，则让k++ 指向右孩子
        if (k+1 < length && arr[k] < arr[k+1]) {
            k ++;
        }
        
        //如果孩子节点大于父节点，则交换位置
        if (arr[k] > val) {
            arr[i] = arr[k];
            i = k; //无法确定k的子节点是否比arr[i]小。 
        } else { 
            break; // 大顶堆的构建是从最后一个非叶子节点来构建的，所以如果此时arr[i]大于两个孩子节点的值，那么说明孩子节点就算有子节点，那也比arr[i]小，所以直接break就行
        }
       
    }
    
    //比较完之后，i指向的是原先最大的那个节点
    arr[i] = val;
}

//交换首尾元素
public void swap(int[] arr, int a, int b) {
    int temp = 0;
    temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

堆排序的时间复杂度为O(nlogn)， 是一种选择排序，并且不稳定。

-------------本文结束感谢您的阅读-------------