排序算法

五一假期复习了几种排序算法，都是用Java实现的。还做了归并排序和堆排序的动画演示，想要的可以和我私聊哈~

1. 冒泡排序

   时间复杂度：O(n^2)

   空间复杂度：O(1)

   稳定算法

   public void myBubbleSort(int arr[]){
       for (int i = 0; i < arr.length-1; i++) {
           for (int j = 0; j < (arr.length-i-1); j++) {
               if(arr[j]>arr[j+1]){  //将较大的数放到后面
                   int t = arr[j];
                   arr[j]=arr[j+1];
                   arr[j+1]= t;
               }
           }
       }
   }

2. 快速排序

   说白了就是给基准数据（枢轴）找其正确索引位置的过程。

   把比基准数大的都放在基准数的右边，把比基准数小的放在基准数的左边，这样就找到了该数据在数组中的正确位置。

   这里找了一个博客：快速排序(三种算法实现和非递归实现)_Maple的博客-CSDN博客_快排非递归

   时间复杂度：O(nlogn)

   空间复杂度：O(n)

   不稳定算法

   public void myQuickSort(int arr[], int lo, int hi) {
          int i = lo;
          int j = hi;
          int temp;
          if (i < j) {	
              temp = arr[i];  // 设置基准，随便取，一般取整组记录的第一个数/最后一个，这里将第一个元素设为基准
              while (i != j) {
                  while (j > i && arr[j] >= temp) {
                      j--;
                  }
                  arr[i] = arr[j];  // 比基准小的放左边
                  while (i < j && arr[i] <= temp) {
                      i++;
                  }
                  arr[j] = arr[i];  // 比基准大的放右边
              }
              arr[i] = temp;  // 到这里，就确定了好基准的位置
              myQuickSort(arr, lo, i - 1);  // 递归，对基准左右两边进行快排
              myQuickSort(arr, i + 1, hi);
          } else {
              return;
          }
      }

3. 归并排序

   时间复杂度：O(nlogn)

   空间复杂度：O(n)

   稳定算法

   归并排序需要一个跟待排序数组同等空间的临时数组，因此，使用归并排序时需要考虑是否有空间上的限制。

   public void mergeArray(int[] arr, int l, int m, int r, int[] temp) {
           int l1 = l, r1 = m;
           int l2 = m + 1, r2 = r;
           int k = 0;  // 用于指示放到temp数组的哪个位置
   
           while (l1 <= r1 && l2 <= r2) {  // 将两个有序序列循环比较, 将较小的填入temp
               if (arr[l1] <= arr[l2]) {
                   temp[k++] = arr[l1++];
               } else {
                   temp[k++] = arr[l2++];
               }
           }
   
           while (l1 <= r1) {  // 多余的元素全部填到temp尾部
               temp[k++] = arr[l1++];
           }
           while (l2 <= r2) {
               temp[k++] = arr[l2++];
           }
   
           for (int i = 0; i < k; i++) {  // 将排好序的数组temp放到arr中
               arr[l + i] = temp[i];
           }
           
       }
   
       public void myMergeSort(int[] arr, int l, int r, int[] temp) {
           if (l < r) {
               int m = (l + r) / 2;
               myMergeSort(arr, l, m, temp);
               myMergeSort(arr, m + 1, r, temp);
               mergeArray(arr, l, m, r, temp);
           }
       }

4. 堆排序

   时间复杂度O(nlogn)

   空间复杂度是O(n)

   不稳定的基于比较的排序算法。

   分为三步，创建堆，调整堆，堆排序。

   创建堆，以数组的形式将堆中所有的数据重新排序，使其成为最大堆/最小堆。

   调整堆，调整过程需要保证堆序性质：在一个二叉堆中任意父节点大于其子节点。

   堆排序，取出位于堆顶的第一个数据（最大堆则为最大数，最小堆则为最小数），放入输出数组B 中，再将剩下的对作调整堆的迭代/重复运算直至输入数组 A中只剩下最后一个元素。

 public void myHeapSort(int[] arr, int n) {
        // 建堆
        for (int i = n / 2; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // 将堆顶元素与顶部元素交换
        for (int i = n - 1; i >= 0; i--) {
            int t = arr[i];
            arr[i] = arr[0];
            arr[0] = t;
            heapify(arr, i, 0);
        }
    }

//建堆
// @param n:数组arr长度
// @param i:堆顶下标
public void heapify(int[] arr, int n, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if (l < n && arr[l] > arr[largest]) {
        largest = l;
    }

    if (r < n && arr[r] > arr[largest]) {
        largest = r;
    }

    if (largest != i) {
        int t = arr[largest];
        arr[largest] = arr[i];
        arr[i] = t;
        heapify(arr, n, largest);
    }

}