一些简单的算法

常见算法的基本思想
  • 穷举
  • 分治
  • 递归
  • 动态规划 子问题往往不是独立的,有事母问题要借助子问题的解来判断,因此把已经计算好的问题记录在表格中,后续如果需要查询一下,可以避免重复计算,这是动态规划的基本思想。
  • 贪心 就是总是做出在当前看来是最好的选择的一种方法,不从问题的整体最优上加以考虑,它所作出的每一步选择只是在某种意义上得局部最优选择
  • 回溯法 深度优先方式系统搜索问题的算法
不同的排序

冒泡排序:

 void bubbleSort(int arr[]) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
      for (int j = 0; j < n - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
          // swap arr[j+1] and arr[j]
          int temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
        }
      }
    }
  }

选择排序:

  void sort(int arr[]) {
    int n = arr.length;

    // One by one move boundary of unsorted subarray
    for (int i = 0; i < n - 1; i++) {
      // Find the minimum element in unsorted array
      int min_idx = i;
      for (int j = i + 1; j < n; j++) {
        if (arr[j] < arr[min_idx]) {
          min_idx = j;
        }
      }

      // Swap the found minimum element with the first
      // element
      int temp = arr[min_idx];
      arr[min_idx] = arr[i];
      arr[i] = temp;
    }
  }

插入排序:

    void sort(int arr[]) {
    int n = arr.length;
    for (int i = 1; i < n; ++i) {
      int key = arr[i];
      int j = i - 1;
  
            /* Move elements of arr[0..i-1], that are 
               greater than key, to one position ahead 
               of their current position */
      while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j = j - 1;
      }
      arr[j + 1] = key;
    }
  }

归并排序:

   void merge(int arr[], int l, int m, int r) {
    // Find sizes of two subarrays to be merged
    int n1 = m - l + 1;
    int n2 = r - m;

    /* Create temp arrays */
    int L[] = new int[n1];
    int R[] = new int[n2];

    /*Copy data to temp arrays*/
    for (int i = 0; i < n1; ++i) {
      L[i] = arr[l + i];
    }
    for (int j = 0; j < n2; ++j) {
      R[j] = arr[m + 1 + j];
    }

    /* Merge the temp arrays */

    // Initial indexes of first and second subarrays
    int i = 0, j = 0;

    // Initial index of merged subarry array
    int k = l;
    while (i < n1 && j < n2) {
      if (L[i] <= R[j]) {
        arr[k] = L[i];
        i++;
      } else {
        arr[k] = R[j];
        j++;
      }
      k++;
    }

    /* Copy remaining elements of L[] if any */
    while (i < n1) {
      arr[k] = L[i];
      i++;
      k++;
    }

    /* Copy remaining elements of R[] if any */
    while (j < n2) {
      arr[k] = R[j];
      j++;
      k++;
    }
  }

  // Main function that sorts arr[l..r] using
  // merge()
  void sort(int arr[], int l, int r) {
    if (l < r) {
      // Find the middle point
      int m = (l + r) / 2;

      // Sort first and second halves
      sort(arr, l, m);
      sort(arr, m + 1, r);

      // Merge the sorted halves
      merge(arr, l, m, r);
    }
  }

快速排序:

    int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1); // index of smaller element
    for (int j = low; j < high; j++) {
      // If current element is smaller than the pivot
      if (arr[j] < pivot) {
        i++;

        // swap arr[i] and arr[j]
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }

    // swap arr[i+1] and arr[high] (or pivot)
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    return i + 1;
  }


  /* The main function that implements QuickSort()
    arr[] --> Array to be sorted,
    low  --> Starting index,
    high  --> Ending index */
  void sort(int arr[], int low, int high) {
    if (low < high) {
            /* pi is partitioning index, arr[pi] is  
              now at right place */
      int pi = partition(arr, low, high);

      // Recursively sort elements before
      // partition and after partition
      sort(arr, low, pi - 1);
      sort(arr, pi + 1, high);
    }
  }

堆排序:

在完全二叉树中,插入的节点与它的父节点相比,如果比父节点小,就交换它们的位置,再往上和父节点相比,如果比父节点小,再交换位置,直到比父节点大为止。 在数组中,插入的节点与n/2位置的节点相比,如果比n/2位置的节点小,就交换它们的位置,再往前与n/4位置的节点相比,如果比n/4位置的节点小,再交换位置,直到比n/(2^x)位置的节点大为止。 这就是插入元素时进行的堆化,也叫自下而上的堆化。

在完全二叉树中,删除堆顶的元素后,把最后一个节点放到堆顶,然后与左右子节点中小的交换位置(因为是小顶堆),依次往下,直到其比左右子节点都小为止。

在数组中,把最后一个元素移到下标为1的位置,然后与下标为2和3的位置对比,发现8比2大,且2是2和3中间最小的,所以与2交换位置;然后再下标为4和5的位置对比,发现8比5大,且5是5和7中最小的,所以与5交换位置,没有左右子节点了,堆化结束。

这就是删除元素时进行的堆化,也叫自上而下的堆化。

堆的插入、删除元素的时间复杂度都是O(log n);建堆的时间复杂度是O(n);堆排序的时间复杂度是O(nlog n);堆排序的空间复杂度是O(1);

 public void sort(int arr[]) {
    int n = arr.length;

    // Build heap (rearrange array)
    for (int i = n / 2 - 1; i >= 0; i--) {
      heapify(arr, n, i);
    }

    // One by one extract an element from heap
    for (int i = n - 1; i > 0; i--) {
      // Move current root to end
      int temp = arr[0];
      arr[0] = arr[i];
      arr[i] = temp;

      // call max heapify on the reduced heap
      heapify(arr, i, 0);
    }
  }

  // To heapify a subtree rooted with node i which is
  // an index in arr[]. n is size of heap
  void heapify(int arr[], int n, int i) {
    int largest = i; // Initialize largest as root
    int l = 2 * i + 1; // left = 2*i + 1
    int r = 2 * i + 2; // right = 2*i + 2

    // If left child is larger than root
    if (l < n && arr[l] > arr[largest]) {
      largest = l;
    }

    // If right child is larger than largest so far
    if (r < n && arr[r] > arr[largest]) {
      largest = r;
    }

    // If largest is not root
    if (largest != i) {
      int swap = arr[i];
      arr[i] = arr[largest];
      arr[largest] = swap;

      // Recursively heapify the affected sub-tree
      heapify(arr, n, largest);
    }
  }

希尔排序:

     /* function to sort arr using shellSort */
  int sort(int arr[]) {
    int n = arr.length;

    // Start with a big gap, then reduce the gap
    for (int gap = n / 2; gap > 0; gap /= 2) {
      // Do a gapped insertion sort for this gap size.
      // The first gap elements a[0..gap-1] are already
      // in gapped order keep adding one more element
      // until the entire array is gap sorted
      for (int i = gap; i < n; i += 1) {
        // add a[i] to the elements that have been gap
        // sorted save a[i] in temp and make a hole at
        // position i
        int temp = arr[i];

        // shift earlier gap-sorted elements up until
        // the correct location for a[i] is found
        int j;
        for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
          arr[j] = arr[j - gap];
        }

        // put temp (the original a[i]) in its correct
        // location
        arr[j] = temp;
      }
    }
    return 0;
  }

二分查找:

    int binarySearch(int arr[], int l, int r, int x) {
    if (r >= l) {
      int mid = l + (r - l) / 2;

      // If the element is present at the
      // middle itself
      if (arr[mid] == x) {
        return mid;
      }

      // If element is smaller than mid, then
      // it can only be present in left subarray
      if (arr[mid] > x) {
        return binarySearch(arr, l, mid - 1, x);
      }

      // Else the element can only be present
      // in right subarray
      return binarySearch(arr, mid + 1, r, x);
    }

    // We reach here when element is not present
    // in array
    return -1;
  }
好玩的
渔舟唱晚,响穷彭蠡之滨;雁阵惊寒,声断衡阳之浦。--[滕王阁序]
相关介绍
参考

> 可在下面留言(需要有 GitHub 账号)