冒泡排序:
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 账号)