六大排序算法：插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序
原创六大排序算法：插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序
原创
1.插入排序插入排序的思路是将数组分成已排序区间和未排序区间。初始已排序区间只有一个元素,然后一次插入未排序区间的元素到已排序区间中,直到全部元素插入已排序区间。
java
public void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int value = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > value) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = value;
}
}该算法的时间复杂度为O(n2),空间复杂度为O(1)。插入排序适用于 already sorted 或几乎已经排序的数据。2.希尔排序 希尔排序通过交换不相邻元素来实现排序,其目的是让数组中任意间隔为h的元素都是有序的。此时数组的性能接近O(n)。然后h逐渐缩小至1,实现基本有序。
java
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++) {
int j = i;
int temp = arr[i];
while (j - gap >= 0 && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j = j - gap;
}
arr[j] = temp;
}
}
} 该算法的最优时间复杂度为O(n),最差时间复杂度为O(n2)。空间复杂度为O(1)。Shell排序适用于大规模数据的排序。3.选择排序选择排序的思路是找出数组中的最小值,将其与数组的第一个元素交换位置。然后在剩余元素中找出最小值,将其与数组的第二个元素交换位置。如此反复,直到将整个数组排序。
java
public void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
} 该算法的时间复杂度和空间复杂度均为O(n2)。选择排序的优点在于数据移动是最少的,但是如果数据量较大,排序速度较慢。
4.冒泡排序冒泡排序的思路是比较相邻的元素,如果顺序错误就把元素交换过来。它从第一个元素开始,比较相邻元素,如果第一个比第二个大,就交换二者位置。然后比较第二个和第三个,以此类推。这样 一趟下来,最后的元素就是最大值或最小值。
java
public void 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;
}
}
}
} 冒泡排序的时间复杂度与空间复杂度均为O(n2)。冒泡排序不是很高效,但简单易理解,可以在非常短时间内完成排序。5.堆排序堆排序使用二叉堆数据结构来实现。其步骤如下:1)将数组构造成二叉大顶堆(每个节点的值都大于其左右节点的值) 2)将堆顶元素和最后一个元素交换 3)将剩余的堆元素再次构造成二叉堆,并重复步骤2,直到大顶堆元素个. 4)将元素逆序输出得到有序序列。
java
public void heapSort(int[] arr) {
if (arr == null || arr.length < 2) return;
for (int i = 0; i < arr.length; i++) {
// 从第一个非叶子节点从下至上,从右至左调整结构
adjustHeap(arr, i, arr.length);
}
// 调整堆结构后,堆顶元素与末尾元素交换,并从堆顶元素开始重复调整堆
for (int i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
adjustHeap(arr, 0, i);
}
}
public void adjustHeap(int[] arr, int i, int length) {
int temp = arr[i];
// 定位左孩子结点和右孩子结点
for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
if (k + 1 < length && arr[k] < arr[k + 1]) { // 右孩子结点的值大于左孩子结点的值
k++;
}
if (arr[k] > temp) {
arr[i] = arr[k];
i = k;
} else {
break;
}
}
arr[i] = temp;
}堆排序的时间复杂度为O(nlogn),空间复杂度为O(1)。堆排序的基本思想是:将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。 将其与末尾元素进行交换,此时末尾就为最大值。 然后将剩余元素重新构造成大顶堆,这样做n-1次,就完成了整个序列的排序。
6.快速排序快速排序使用分治法来把一个数组分为两个子数组,其步骤如下:1)从数组中挑出一个元素作为基准(pivot),通常选择第一个、最后一个或中间一个元素。2)分割:所有比基准值小的元素挪到基准前面,所有比基准值大的元素挪到基准后面。3)递归地对基准值前后的两个子数组进行快速排序,直到数组已经完全排序。```java
public void quickSort(int[] arr, int left, int right) {
if (left < right) {
int pivot = partition(arr, left, right);
quickSort(arr, left, pivot - 1);
quick quickSort(arr, pivot + 1, right);
}
}
public int partition(int[] arr, int left, int right) {
int pivot = arr[left];
int i = left;
int j = right;
while (i < j) {
while (arr[i] <= pivot && i < right)
i++;
while (arr[j] > pivot && j > left)
j--;
if (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
arr[left] = arr[j];
arr[j] = pivot;
return j;
}快速排序的时间复杂度为O(nlogn),空间复杂度为O(logn)。快速排序思想简单但实现比较巧妙,是常用的高效排 序算法。快速排序采用分治法策略,以第一个元素为主元,将数组分成两半,左半部的值都比主元小,右半部的值都比主元大。然后递归地排序两个子数组。快速排序最重要的是partition()这个步骤,它可以确保主元左边的值都比主元小,主元右边的值都比主元大。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。