文章目录
- 一、冒泡排序
- 1、效率表现和适用范围
- 2、算法实现
- 二、选择排序
- 1、效率表现和适用范围
- 2、算法实现
- 三、插入排序
- 1、效率表现和适用范围
- 2、算法实现
- 四、shell排序
- 1、效率表现和适用范围
- 2、算法实现
- 五、归并排序
- 1、效率表现和适用范围
- 2、算法实现
- 六、快速排序
- 1、效率表现和适用范围
- 2、算法实现
- 七、堆排序
- 1、效率表现和适用范围
- 2、算法实现
本文简单的介绍了java常见的几种排序。
所有的排序均是一个数组由小到大进行排序。
一、冒泡排序
1、效率表现和适用范围
效率 O(n²)
适用于排序小列表
2、算法实现
public void bubbleSortArray(int[] a) {
int n = a.length;
for (int i = 1; i < n; i++) {
for (int j = 0; i < n - i; j++) {
// 比较交换相邻元素
if (a[j] > a[j + 1]) {
int temp;
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
二、选择排序
1、效率表现和适用范围
效率O(n²)
适用于排序小的列表
2、算法实现
public void selectSortArray(int[] a) {
int n = a.length;
int min_index;
for (int i = 0; i < n - 1; i++) {
min_index = i;
for (int j = i + 1; j < n; j++)// 每次扫描选择最小项
if (a[j] < a[min_index])
min_index = j;
if (min_index != i)// 找到最小项交换,即将这一项移到列表中的正确位置
{
int temp;
temp = a[i];
a[i] = a[min_index];
a[min_index] = temp;
}
}
}
三、插入排序
1、效率表现和适用范围
最佳效率O(n);最糟效率O(n²)与冒泡、选择相同
适用于排序小列表
若列表基本有序,则插入排序比冒泡、选择更有效率
2、算法实现
void insertSortArray(int[] a) {
int n = a.length;
for (int i = 1; i < n; i++)// 循环从第二个数组元素开始,因为a[0]作为最初已排序部分
{
int temp = a[i];// temp标记为未排序第一个元素
int j = i - 1;
while (j >= 0 && a[j] > temp)/* 将temp与已排序元素从小到大比较,寻找temp应插入的位置 */
{
a[j + 1] = a[j];
j--;
}
a[j + 1] = temp;
}
}
四、shell排序
1、效率表现和适用范围
适用于排序小列表。
效率估计O(nlog2n)~O(n1.5),取决于增量值的最初大小。建议使用质数作为增量值,因为如果增量值是2的幂,则在下一个通道中会再次比较相同的元素。
壳(Shell)排序改进了插入排序,减少了比较的次数。是不稳定的排序,因为排序过程中元素可能会前后跳跃
2、算法实现
void shellSortArray(int[] a) {
int n = a.length;
for (int incr = 3; incr < 0; incr--)// 增量递减,以增量3,2,1为例
{
for (int L = 0; L < (n - 1) / incr; L++)// 重复分成的每个子列表
{
for (int i = L + incr; i < n; i += incr)// 对每个子列表应用插入排序
{
int temp = a[i];
int j = i - incr;
while (j >= 0 && a[j] > temp) {
a[j + incr] = a[j];
j -= incr;
}
a[j + incr] = temp;
}
}
}
}
五、归并排序
1、效率表现和适用范围
效率O(nlogn),归并的最佳、平均和最糟用例效率之间没有差异。
适用于排序大列表,基于分治法
2、算法实现
public static void merge(int[] arr, int low, int mid, int high, int[] tmp) {
int i = 0;
int j = low, k = mid + 1; // 左边序列和右边序列起始索引
while (j <= mid && k <= high) {
if (arr[j] < arr[k]) {
tmp[i++] = arr[j++];
} else {
tmp[i++] = arr[k++];
}
}
// 若左边序列还有剩余,则将其全部拷贝进tmp[]中
while (j <= mid) {
tmp[i++] = arr[j++];
}
while (k <= high) {
tmp[i++] = arr[k++];
}
for (int t = 0; t < i; t++) {
arr[low + t] = tmp[t];
}
}
/**
* 效率O(nlogn),归并的最佳、平均和最糟用例效率之间没有差异。 适用于排序大列表,基于分治法
*
* @param arr
* @param low
* @param high
* @param tmp
*/
public static void mergeSort(int[] arr, int low, int high, int[] tmp) {
if (low < high) {
int mid = (low + high) / 2;
mergeSort(arr, low, mid, tmp); // 对左边序列进行归并排序
mergeSort(arr, mid + 1, high, tmp); // 对右边序列进行归并排序
merge(arr, low, mid, high, tmp); // 合并两个有序序列
}
}
六、快速排序
1、效率表现和适用范围
快速排序的算法思想:选定一个枢纽元素,对待排序序列进行分割,分割之后的序列一个部分小于枢纽元素,一个部分大于枢纽元素,再对这两个分割好的子序列进行上述的过程。
平均效率O(nlogn),适用于排序大列表。
此算法的总时间取决于枢纽值的位置;选择第一个元素作为枢纽,可能导致O(n²)的最糟用例效率。若数基本有序,效率反而最差。选项中间值作为枢纽,效率是O(nlogn)。
基于分治法。
2、算法实现
public static void quickSort(int[] arr, int low, int high) {
int i, j, temp, t;
if (low > high) {
return;
}
i = low;
j = high;
// temp就是基准位
temp = arr[low];
while (i < j) {
// 先看右边,依次往左递减
while (temp <= arr[j] && i < j) {
j--;
}
// 再看左边,依次往右递增
while (temp >= arr[i] && i < j) {
i++;
}
// 如果满足条件则交换
if (i < j) {
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
// 最后将基准为与i和j相等位置的数字交换
arr[low] = arr[i];
arr[i] = temp;
// 递归调用左半数组
quickSort(arr, low, j - 1);
// 递归调用右半数组
quickSort(arr, j + 1, high);
}
七、堆排序
最大堆:后者任一非终端节点的关键字均大于或等于它的左、右孩子的关键字,此时位于堆顶的节点的关键字是整个序列中最大的。
思想:
(1)令i=l,并令temp= kl ;
(2)计算i的左孩子j=2i+1;
(3)若j<=n-1,则转(4),否则转(6);
(4)比较kj和kj+1,若kj+1>kj,则令j=j+1,否则j不变;
(5)比较temp和kj,若kj>temp,则令ki等于kj,并令i=j,j=2i+1,并转(3),否则转(6)
(6)令ki等于temp,结束。
1、效率表现和适用范围
堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。
由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。
堆排序是就地排序,辅助空间为O(1),它是不稳定的排序方法。
- 堆排序与直接插入排序的区别
1、直接选择排序中,为了从R[1…n]中选出关键字最小的记录,必须进行n-1次比较,然后在R[2…n]中选出关键字最小的记录,又需要做n-2次比较。事实上,后面的n-2次比较中,有许多比较可能在前面的n-1次比较中已经做过,但由于前一趟排序时未保留这些比较结果,所以后一趟排序时又重复执行了这些比较操作。
2、堆排序可通过树形结构保存部分比较结果,可减少比较次数。
2、算法实现
public static void heapSort(int[] arr) {
int temp;
System.out.println("从后向前构建堆");
//从后面的非叶子结点进行调整数组为大顶堆
for (int i = arr.length / 2 - 1; i >= 0; i--) {
System.out.println("非叶子结点:" + i);
bigTopPile(arr, i, arr.length);
}
System.out.println("从根节点开始构建堆");
for (int j = arr.length - 1; j > 0; j--) {
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
System.out.println("确认下标为" + j + ":" + Arrays.toString(arr));
// 从根节点开始调整数据为大顶堆
bigTopPile(arr, 0, j);
}
}
/**
* 将数组变为一个大顶堆
*
* @param arr 数组
* @param nonLeafNode 非叶子结点在数组中的下标
* @param length 调整的数组长度
*/
public static void bigTopPile(int[] arr, int nonLeafNode, int length) {
System.out.println("构建前数组:" + Arrays.toString(arr));
//保存非叶子结点
int temp = arr[nonLeafNode];
System.out.println("非叶子结点数据:" + temp);
// index = nonLeafNode * 2 + 1 index为非叶子结点的左子结点
for (int index = nonLeafNode * 2 + 1; index < length; index = index * 2 + 1) {
System.out.println("左子节点:" + index);
//左子节点小于右子节点 右子节点就是左子节点加1
if (index + 1 < length && arr[index] < arr[index + 1]) {
System.out.println("左子节点小于右子节点,指针指向右子节点");
//左子节点小于右子节点 那么将index此时指向右子节点
index++;
}
//如果子节点大于父节点 则进行交换
if (arr[index] > temp) {
System.out.println("子节点大于父节点,进行交换");
arr[nonLeafNode] = arr[index];
nonLeafNode = index;
} else {
break;
}
}
arr[nonLeafNode] = temp;
System.out.println("构建后数组:" + Arrays.toString(arr));
System.out.println();
}
以上,简单的介绍了java中常见的集中排序算法以及各自的效率表现、应用场景。