public void heapSort(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 heapvoid 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); }}
public void quickSort(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 quickSort(arr, low, pi-1); quickSort(arr, pi+1, high); }}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;}
public void mergeSort(int[] arr, int l, int r) { if (l < r) { // Find the middle point int m = (l+r)/2; // Sort first and second halves mergeSort(arr, l, m); mergeSort(arr , m+1, r); // Merge the sorted halves merge(arr, l, m, r); }}// Merges two subarrays of arr[].// First subarray is arr[l..m]// Second subarray is arr[m+1..r]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++; }}
public 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; }}
public void shellSort(int[] arr) { int n = arr.length; for (int gap = n/2; gap > 0; gap /= 2) { for (int i = gap; i < n; i += 1) { int temp = arr[i]; int j; for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) arr[j] = arr[j - gap]; arr[j] = temp; } }}
public int linearSearch(int[] arr, int target) { for (int i = 0; i < arr.length; i++) { if (arr[i] == target) { return i; // 返回找到的元素的索引 } } return -1; // 如果没有找到，返回-1}
2. 二分搜索（Binary Search）
原理：二分搜索是一种在有序数组中查找特定元素的高效算法。
3.3 时间复杂度
最好情况：(O(n))
平均情况：(O(n^2))
最坏情况：(O(n^2))
3.4 稳定性
稳定
3.5 Java代码实现
public void insertionSort(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; }}
public void selectionSort(int[] arr) { int n = arr.length; for (int i = 0; i < n-1; i++) { int minIdx = i; for (int j = i+1; j < n; j++) if (arr[j] < arr[minIdx]) minIdx = j; // Swap the found minimum element with the first element int temp = arr[minIdx]; arr[minIdx] = arr[i]; arr[i] = temp; }}
public int sequentialIndexLookup(int[] arr, int target) { for (int i = 0; i < arr.length; i++) { if (arr[i] == target) { return i; // 返回目标元素的索引 } } return -1; // 如果没有找到，返回-1}
