冒泡排序
它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。以此类推,直到所有元素均排序完毕。
- 时间复杂度:O(n2)
- 空间复杂度:O(1)
public int[] bubbleSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
选择排序
首先在未排序序列中找到最小(大)元素,存放到起始位置,然后再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
- 时间复杂度:O(n2)
- 空间复杂度:O(1)
public int[] selectionSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
return arr;
}
插入排序
它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
- 时间复杂度:O(n2)
- 空间复杂度:O(1)
public int[] insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int preIndex = i - 1;
int current = arr[i];
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
return arr;
}
快速排序
通过一趟排序将待排数据录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
- 算法步骤:
- 从数列中挑出一个元素,称为 “基准”(pivot)
- 将所有比基准值小的元素摆放在基准值前面,所有比基准值大的元素摆在基准值的后面(相同的数可以到任一边)
- 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序
- 复杂度:
- 时间复杂度:O(nlogn)
- 空间复杂度:O(logn)
public void quickSort(int[] arr, int start, int end) {
//递归出口
if (start > end) return;
int left = start;
int right = end;
int pivot = arr[left];
while (left != right) {
//从后向前找到比基准数小的位置
while (left < right && arr[right] >= pivot) {
right--;
}
//从前向后找到比基准数大的位置
while (left < right && arr[left] <= pivot) {
left++;
}
//如果不是同一个位置则交换两个数
if (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
//调整基准数的位置
arr[start] = arr[left];
arr[left] = pivot;
quickSort(arr, 0, left - 1);
quickSort(arr, left + 1, end);
}
网友评论