首页 / JAVA / java实现各种排序算法及比较
java实现各种排序算法及比较
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了java实现各种排序算法及比较,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含4748字,纯文字阅读大概需要7分钟。
内容图文
常见排序算法包括以下七种:选择排序、冒泡排序、插入排序、快速排序、希尔排序、堆排序、归并排序。
在学习具体算法实现并进行比较前,先来学习算法比较的几个维度。
一是稳定性
所谓稳定性,是指值相等的两个元素在排序前后是否会发生位置的交换。如果不会发生交换,则认为是稳定的算法;反之,则认为是不稳定的排序算法。
二是时间复杂度,指执行算法所需的时间长短。简单说就是算法执行的快慢程序。
三是空间复杂度,指执行算法所占用的内存大小。
有了这些基本概念,下面就来看以上七种排序算法的java版实现
/**
* <一句话功能简述>
*/
public
class
AllSort {
/**
* 快速排序<br/>
* 不稳定排序,时间复杂度O(nlogn)
*
* @param a
* @param left
* @param right
* @return
*/
public
static
void
quickSort(int[] a, int left, int right) {
if (left >= right)
return;
int i, j, temp;
i = left;
j = right;
temp = a[left];
while (i != j) {
while (a[j] >= temp && i < j)
j--;
while (a[i] <= temp && i < j)
i++;
if (i < j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
j--;
}
}
a[left] = a[i];
a[i] = temp;
if (left < i - 1)
quickSort(a, left, i - 1);
if (i + 1 < right)
quickSort(a, i + 1, right);
}
/**
* 选择排序<br/>
* 不稳定排序,时间复杂度为O(n2)
*
* @param a
* @return
*/publicstaticvoidchoseSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
int min_index = i;
for (int j = i + 1; j < a.length; j++) {
if (a[min_index] > a[j]) {
min_index = j;
}
}
if (i != min_index) {
int temp = a[i];
a[i] = a[min_index];
a[min_index] = temp;
}
}
}
/**
* 冒泡排序<br/>
* 稳定排序,时间复杂度为O(n2)
*
* @param a
* @return
*/publicstaticvoidbubbleSort(int[] a) {
for (int i = 1; i < a.length; i++) {
for (int j = 0; j < a.length - i; j++) {
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
/**
* 直接插入排序<br/>
* 稳定排序,时间复杂度O(n2)
*
* @param a
* @return
*/publicstaticvoidinsertSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int temp = a[i];
int pos = i - 1;
while (pos >= 0 && a[pos] > temp) {
a[pos + 1] = a[pos];
pos--;
}
a[pos + 1] = temp;
}
}
/**
* 希尔排序<br/>
* 不稳定排序,时间复杂度O(nlogn)
*
* @param a
* @return
*/publicstaticvoidshellSort(int[] a) {
int d = a.length / 2;
while (d >= 1) {
for (int i = 0; i < d; i++) {
for (int j = i + d; j < a.length; j = j + d) {
int temp = a[j];
int pos = j - d;
while (pos >= 0 && a[pos] > temp) {
a[pos + d] = a[pos];
pos -= d;
}
a[pos + d] = temp;
}
}
d = d / 2;
}
}
/**
* 归并排序<br/>
* 稳定排序,时间复杂度O(nlogn),速度仅次于快速排序
*
* @param a
* @param left
* @param right
* @return
*/publicstaticvoidmergeSort(int[] a, int left, int right) {
if (left < right) {
int middle = (left + right) / 2;
// 对左边进行递归
mergeSort(a, left, middle);
// 对右边进行递归
mergeSort(a, middle + 1, right);
// 合并
merge(a, left, middle, right);
}
}
privatestaticvoidmerge(int[] a, int left, int middle, int right) {
int[] tmpArr = newint[right - left + 1];
int pos = 0;
int i = left;// 左边起始位置int j = middle + 1; // 右边起始位置while (i <= middle && j <= right) {
// 从两个数组中选取较小的数放入中间数组if (a[i] <= a[j]) {
tmpArr[pos++] = a[i++];
} else {
tmpArr[pos++] = a[j++];
}
}
// 将剩余的部分放入中间数组while (i <= middle) {
tmpArr[pos++] = a[i++];
}
while (j <= right) {
tmpArr[pos++] = a[j++];
}
// 将中间数组复制回原数组int start = 0;
while (left <= right) {
a[left++] = tmpArr[start++];
}
}
/**
* 堆排序<br/>
* 不稳定排序,时间复杂度O(nlogn)
* @param a
* @return
*/publicstaticvoidheapSort(int[] a) {
int lastIndex = a.length - 1;
for (int i = 0; i < lastIndex; i++) {
// 建堆
buildMaxHeap(a, lastIndex - i);
// 交换堆顶和最后一个元素
swap(a, 0, lastIndex - i);
// System.out.println(Arrays.toString(a));
}
}
privatestaticvoidbuildMaxHeap(int[] data, int lastIndex) {
// 从lastIndex处节点(最后一个节点)的父节点开始for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
// k保存正在判断的节点int k = i;
// 如果当前k节点的子节点存在while (k * 2 + 1 <= lastIndex) {
// k节点的左子节点的索引int biggerIndex = 2 * k + 1;
// 如果biggerIndex小于lastIndex,即biggerIndex+1代表的k节点的右子节点存在if (biggerIndex < lastIndex) {
// 若果右子节点的值较大if (data[biggerIndex] < data[biggerIndex + 1]) {
// biggerIndex总是记录较大子节点的索引
biggerIndex++;
}
}
// 如果k节点的值小于其较大的子节点的值if (data[k] < data[biggerIndex]) {
// 交换他们
swap(data, k, biggerIndex);
// 将biggerIndex赋予k,开始while循环的下一次循环,重新保证k节点的值大于其左右子节点的值
k = biggerIndex;
} else {
break;
}
}
}
}
privatestaticvoidswap(int[] data, int i, int j) {
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
publicstaticvoidmain(String[] args) {
Random random = new Random();
int[] a = newint[20];
for (int i = 0; i < a.length; i++) {
a[i] = random.nextInt(20);
}
//quickSort(a, 0, a.length - 1);//mergeSort(a, 0, a.length - 1);//shellSort(a);//heapSort(a);//choseSort(a);//bubbleSort(a);//insertSort(a);
System.out.println(Arrays.toString(a));
}
}
各排序算法比较如下图
这个是摘自网上的比较,仅供参考。
我对有些项持怀疑态度,例如归并排序,个人认为空间复杂度不应该是O(1),而应该是O(nlog2n)。而快速排序的空间复杂度是O(1)。
原文:http://blog.csdn.net/tang9140/article/details/46409739
内容总结
以上是互联网集市为您收集整理的java实现各种排序算法及比较全部内容,希望文章能够帮你解决java实现各种排序算法及比较所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。