今天重温了以前学过的几种排序，现总结如下：
冒泡排序：
package com.goole.rank;
/**
* 冒泡排序（稳定，时间复杂度O(n*n),空间复杂度O(1)）
* @author darren
*
*/
public class BubbleSort {
public static void main(String[] args) {
int[] a = {4, 8, 9, 3, 0, 5, 7, 6, 2};
bubbleSort(a);
print(a);
}
private static void bubbleSort(int[] a) {
for(int i=0; i<a.length-1; i++) {
boolean flag = false;
for(int j=a.length-1; j>i; j--) {
if(a[j]<a[j-1]) {
swap(a, j-1, j);
flag = true;
}
}
if(!flag) {
return;
}
}
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
private static void print(int[] a) {
for(int i=0; i<a.length; i++) {
if(i==a.length-1) {
System.out.print(a[i]);
}else {
System.out.print(a[i]+", ");
}
}
}
}
直接插入排序：
package com.goole.rank;
/**
* 直接插入排序(稳定，时间复杂度O(n*n),空间复杂度O(1))
* @author darren
*
*/
public class InsertSort {
public static void main(String[] args) {
int[] a = {4, 8, 9, 3, 0, 5, 7, 6, 2};
insertsort(a);
print(a);
}
private static void print(int[] a) {
for(int i=0; i<a.length; i++) {
if(i==a.length-1) {
System.out.print(a[i]);
}else {
System.out.print(a[i]+", ");
}
}
}
private static void insertsort(int[] a) {
for(int i=1; i<=a.length-1; i++) {
if(a[i]<a[i-1]) {
int p = a[i];
int j;
for(j=i-1; j>=0&&a[j]>p; j--) {
a[j+1] = a[j];
}
a[j+1] = p;
}
}
}
}
折半插入排序：
package com.goole.rank;
/**
* 折半插入排序（稳定，时间复杂度O(n*n),空间复杂度O(1)）
* 和直接插入排序相比仅仅少了元素的比较次数
* @author darren
*
*/
public class HalfInsertSort {
public static void main(String[] args) {
int[] a = {4, 8, 9, 3, 0, 5, 7, 6, 2};
halfInsertSort(a);
print(a);
}
private static void halfInsertSort(int[] a) {
for(int i=1; i<=a.length-1; i++) {
if(a[i]<a[i-1]) {
int p = a[i];
int low=0, high=i-1;
while(low<=high) {
int mid = (low+high)/2;
if(p<a[mid]) {
high = mid-1;
}else {
low = mid+1;
}
}
int j=i-1;
for(; j>=high+1; j--) {
a[j+1] = a[j];
}
//a[j+1] = p;
a[high+1] = p;
}
}
}
private static void print(int[] a) {
for(int i=0; i<a.length; i++) {
if(i==a.length-1) {
System.out.print(a[i]);
}else {
System.out.print(a[i]+", ");
}
}
}
}
归并排序：
package com.goole.rank;
/**
* 归并排序（稳定，时间复杂度O(n*log(n)),空间复杂度O(n)）
* @author darren
*
*/
public class MergeSort {
public static void main(String[] args) {
int[] a = {4, 8, 9, 3, 0, 5, 7, 6, 2};
int[] tempArr = new int[a.length];
mergeSort(a, tempArr, 0, a.length-1);
print(a);
}
private static void mergeSort(int[] a, int[] tempArr, int low, int high) {
if(low<high) {
int mid = (low+high)/2;
mergeSort(a, tempArr, low, mid);
mergeSort(a, tempArr, mid+1, high);
merge(a, tempArr, low, mid+1, high);
}
}
private static void merge(int[] a, int[] tempArr, int leftPos, int rightPos, int rightEnd) {
int leftEnd = rightPos-1;
int tempPos = leftPos;
int num = rightEnd-leftPos+1;
while(leftPos<=leftEnd&&rightPos<=rightEnd) {
if(a[leftPos]<a[rightPos]) {
tempArr[tempPos++] = a[leftPos++];
}else {
tempArr[tempPos++] = a[rightPos++];
}
}
while(leftPos<=leftEnd) {
tempArr[tempPos++] = a[leftPos++];
}
while(rightPos<=rightEnd) {
tempArr[tempPos++] = a[rightPos++];
}
for(int i=0; i<num; i++,rightEnd--) {
a[rightEnd] = tempArr[rightEnd];
}
}
private static void print(int[] a) {
for(int i=0; i<a.length; i++) {
if(i==a.length-1) {
System.out.print(a[i]);
}else {
System.out.print(a[i]+", ");
}
}
}
}
堆排序：
package com.goole.rank;
/**
* 堆排序（不稳定，时间复杂度O(nlog(n), 空间复杂度O(1)）
* @author darren
*
*/
public class HeapSort {
public static void main(String[] args) {
int[] a = {4, 8, 9, 3, 0, 5, 7, 6, 2};
heapSort(a);
print(a);
}
private static void heapSort(int[] a) {
//建堆过程
for(int i=a.length/2; i>=0; i--) {
percDown(a, i, a.length);
}
//删除过程
for(int i=a.length-1; i>0; i--) {
swap(a, 0, i);
percDown(a, 0, i);
}
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
private static void percDown(int[] a, int i, int n) {
int child = 0;
int temp;
for(temp=a[i]; leftChild(i)<n; i=child) {
child = leftChild(i);
if(leftChild(i)!=n-1&&a[child]<a[child+1]) {
child++;
}
if(temp<a[child]) {
a[i] = a[child];
}else {
break;
}
}
a[i] = temp;
}
private static int leftChild(int i) {
return 2*i+1;
}
private static void print(int[] a) {
for(int i=0; i<a.length; i++) {
if(i==a.length-1) {
System.out.print(a[i]);
}else {
System.out.print(a[i]+", ");
}
}
}
}
快速排序：
package com.goole.rank;
/**
* 快速排序（不稳定，时间复杂度O(n*log(n)),空间复杂度O(log(n))）
* @author darren
*
*/
public class QuickSort {
public static void main(String[] args) {
int[] a = {4, 8, 9, 3, 0, 5, 7, 6, 2};
quickSort(a, 0, a.length-1);
print(a);
}
private static void quickSort(int[] a, int low, int high) {
if(low<high) {
int mid = getMiddle(a, low, high);
quickSort(a, 0, mid-1);
quickSort(a, mid+1, high);
}
}
private static int getMiddle(int[] a, int low, int high) {
int pivot = a[low];
while(low<high) {
while(a[high]>=pivot&&high>low) {
high--;
}
a[low] = a[high];
while(a[low]<=pivot&&high>low) {
low++;
}
a[high] = a[low];
}
a[low] = pivot;
return low;
}
private static void print(int[] a) {
for(int i=0; i<a.length; i++) {
if(i==a.length-1) {
System.out.print(a[i]);
}else {
System.out.print(a[i]+", ");
}
}
}
}
简单选择排序：
package com.goole.rank;
/**
* 简单选择排序（不稳定，时间复杂度O(n*n),空间复杂度O(1)）
* @author darren
*
*/
public class SelectSort {
public static void main(String[] args) {
int[] a = {4, 8, 9, 3, 0, 5, 7, 6, 2};
selectSort(a);
print(a);
}
private static void selectSort(int[] a) {
for(int i=0; i<a.length-1; i++) {
for(int j=i+1; j<=a.length-1; j++) {
if(a[j]<a[i]) {
swap(a, i, j);
}
}
}
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
private static void print(int[] a) {
for(int i=0; i<a.length; i++) {
if(i==a.length-1) {
System.out.print(a[i]);
}else {
System.out.print(a[i]+", ");
}
}
}
}
希尔排序：
package com.goole.rank;
/**
* 希尔排序（不稳定，时间复杂度<O(n*n),空间复杂度O(1)）
* @author darren
*
*/
public class ShellSort {
public static void main(String[] args) {
int[] a = {4, 8, 9, 3, 0, 5, 7, 6, 2};
shellSort(a);
print(a);
}
private static void shellSort(int[] a) {
for(int gap=a.length/2; gap>0; gap/=2) {
for(int i=gap; i<a.length; i++) {
int temp = a[i];
int j=i;
for(; j>=gap&&temp<a[j-gap]; j-=gap) {
a[j] = a[j-gap];
}
a[j] = temp;
}
}
}
private static void print(int[] a) {
for(int i=0; i<a.length; i++) {
if(i==a.length-1) {
System.out.print(a[i]);
}else {
System.out.print(a[i]+", ");
}
}
}
}
相关推荐
数据结构与算法是计算机科学的基础，对于理解和设计高效的软件至关重要。C语言因其高效、底层特性，常被用于实现数据结构和算法，使得程序更接近硬件，性能更优。本资源"数据结构与算法分析--C语言描述"是针对数据...
JS 数据结构与算法.pdf 本书主要介绍了 JavaScript 语言的基础知识，包括数据结构和算法。以下是该书的详细知识点： 一、JavaScript 基础知识 * 变量和数据类型 * 运算符和控制结构 * 函数和对象 * 数组和字符串 ...
数据结构与算法是计算机科学领域的两大基石，它们几乎无处不在地影响着我们的日常生活和工作。尽管很多人可能会有这样的误解，认为数据结构和算法是高深且脱离实际工作的理论知识，只在面试或者特定情况下才会用到。...
资源名称：数据结构与算法视频课程（59集）资源目录：【】mysql视频教程第41讲存储过程【】数据结构与算法_1.10算法的评价【】数据结构与算法_1.1编程的灵魂：数据结构 算法【】数据结构与算法_1.2算法的作用：猜...
在编程领域，数据结构与算法是核心组成部分，它们直接影响到程序的效率和性能。Java作为广泛应用的编程语言，其在实现数据结构和算法时有着丰富的库支持和优秀的可读性。下面将对标题和描述中提到的一些关键知识点...
PTA-数据结构与算法题目集 PTA-数据结构与算法题目集 PTA-数据结构与算法题目集 PTA-数据结构与算法题目集 PTA-数据结构与算法题目集 PTA-数据结构与算法题目集 PTA-数据结构与算法题目集 PTA-数据结构与算法题目集 ...
python数据结构与算法python数据结构与算法python数据结构与算法python数据结构与算法python数据结构与算法python数据结构与算法python数据结构与算法python数据结构与算法python数据结构与算法python数据结构与算法...
《Java数据结构与算法第二版源代码》是一个深入学习Java编程和算法的重要资源，它包含了丰富的实例和程序，旨在帮助开发者提升对数据结构和算法的理解与应用能力。在这个压缩包中，有两个主要的子文件：...
《数据结构与算法分析:Java语言描述 第2版 》是国外数据结构与算法分析方面的经典教材 使用卓越的Java编程语言作为实现工具讨论了数据结构（组织大量数据的方法）和算法分析（对算法运行时间的估计） 随着计算机速度...
数据结构与算法是计算机科学的核心内容，它们在解决实际问题、提高程序效率以及编写高质量软件中扮演着至关重要的角色。数据结构是计算机存储、组织数据的方式，它可以帮助我们在计算机中以更加高效和合适的方式表示...
数据结构与算法.pdf 数据结构是计算机科学中的一门重要课程，涉及到数据的逻辑结构、存储结构、算法等方面的知识。在本文件中，我们将详细介绍数据结构的基本概念、逻辑结构、存储结构、抽象数据类型、算法等知识点...
### 数据结构与算法(C#版)关键知识点解析 #### 一、引言 《数据结构与算法(C#版)》是一本旨在通过C#语言来介绍数据结构与算法原理的书籍。随着C#语言和.NET Framework的发展，这本书不仅填补了国内以C#语言讲解...
数据结构与算法是计算机科学中的核心课程，它探讨如何有效地组织和处理数据，以及如何设计和分析解决问题的算法。这份“数据结构与算法-PPT课件”提供了丰富的学习材料，涵盖了多个关键主题。 首先，我们要了解数据...
《数据结构与算法分析C++语言描述第四版》是一本深度探讨数据结构和算法的经典教材。这本书由Mark Allen Weiss撰写，旨在帮助读者理解和掌握如何在C++编程环境中有效地设计和实现数据结构及算法。第四版更新了内容，...
数据结构与算法(C#).PDF及代码 第1章 Collections类、泛型类和Timing类概述 第2章 数组和ArrayList 第3章 基础排序算法 第4章 基础查找算法 第5章 栈和队列 第6章 BitArray类 第7章 字符串、String类和StringBuioder...