比较一览
|
排序法
|
最优时间
|
平均复杂度
|
最差情形
|
稳定度
|
额外空间
|
备注
|
类型
|
|
选择
|
O(n2)
|
O(n2)
|
O(n2)
|
不稳定
|
O(1)
|
n小时较好
|
选择排序 |
|
冒泡
|
0-O(n)
|
O(n2)
|
O(n2)
|
稳定
|
O(1)
|
n小时较好
|
交换排序
|
|
插入
|
O(n)
|
O(n2)
|
O(n2)
|
稳定
|
O(1)
|
大部分已排序时
|
插入排序
|
|
Shell
|
O(n)
|
依赖步长串行
|
O(ns) 1<s<2
|
不稳定
|
O(n)
|
s是所选分组
|
插入排序
|
|
快速
|
O(nlogn)
|
O(nlogn)
|
O(n2)
|
不稳定
|
O(nlogn)
|
n大时较好
|
交换排序
|
|
归并
|
O(n)
|
O(nlogn)
|
O(nlogn)
|
稳定
|
O(1)-O(n)
|
n大时较好
|
归并排序
|
|
堆
|
O(nlogn)
|
O(nlogn)
|
O(nlogn)
|
不稳定
|
O(1)-O(n)
|
n大时较好
|
选择排序
|
1. 快速排序
介绍：
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序n个项目要Ο(nlogn)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(nlogn)
算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来，且在大部分真实世界的数据，可以决定设计的选择，减少所需时间的二次方项之可能性。
步骤：
- 从数列中挑出一个元素，称为 “基准”（Pivot），
-
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
-
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
代码：
public class QuitSort {
static int cpNum = 0;
static int swapNum = 0;
public static void main(String[] args) {
int[] a = {5,44,3,64,3,64,34,45,4,112};
QuitSort.quitSort(a,0,a.length-1);
System.out.println("数组大小:"+a.length+" 比较次数:"+cpNum+" 交换次数："+swapNum);
for (int i : a) {
System.out.print(i+"--");
}
}
public static void quitSort(int[] a,int start ,int end) {
if (start >= end )
return;
int i = start;
int j = end;
int key = a[start];
while (i < j) {
for (; j > i; j--) {
cpNum++;
if (a[j] < key) {
swapNum++;
a[i] = a[j];
break;
}
}
for (; i < j; i++) {
cpNum++;
if (a[i] > key) {
swapNum++;
a[j] = a[i];
break;
}
}
}
a [i] = key;
quitSort(a,start,i-1);//sort left
quitSort(a,i+1,end);//sort left [
}
}
2. 归并排序
介绍：
归并排序（Merge sort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide
and Conquer）的一个非常典型的应用
步骤：
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤3直到某一指针达到序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
代码：
import java.util.Arrays;
/**
* 归并排序
*
* 空间换时间
* Cworst(n) = O(n log n)
* @author stephen
*
*/
public class MergeSort {
/**
* @param args
*/
public static void main(String[] args) {
int[] a = {5,4,3,2,1};
//int[] a = { 5, 44, 9, 64, 3, 64, 34, 45, 3, 112 };
sort(a);
System.out.println("比较次数:" + cpNum);
System.out.println("移动次数:" + moveNum);
for (int i : a) {
System.out.print(i + "--");
}
}
static int cpNum = 0;
static int moveNum = 0;
public static void sort(int[] a) {
int t;
int length = a.length;
int middle = (length) / 2;
if (length > 1) {
int[] b = Arrays.copyOfRange(a, 0, middle);
int[] c = Arrays.copyOfRange(a, middle, length);
moveNum += length;
sort(b);
sort(c);
merge(a, b, c);
}
}
private static void merge(int[] a, int[] b, int[] c) {
int i = 0, j = 0, k = 0;
while (i < b.length && j < c.length) {
cpNum++;
if (b[i] > c[j]) {
a[k] = c[j];
k++;
j++;
moveNum++;
} else {
a[k] = b[i];
k++;
i++;
moveNum++;
}
}
if (i == b.length) {
while (j < c.length) {
a[k] = c[j];
j++;
k++;
moveNum++;
}
} else {
while (i < b.length) {
a[k] = b[i];
i++;
k++;
moveNum++;
}
}
}
}
3. 堆排序
介绍：
堆积排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
步骤：
（比较复杂，略）
4. 选择排序
介绍：
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。
代码：
/**
* C(c) = n*(n-1)/2 O(n^2)
* @author stephenluu
*
*/
public class SelectionSort {
public static void main(String[] args) {
// int[] a = {5,4,3,2,1};
int[] a = { 5, 44, 9, 64, 3, 64, 34, 45, 3, 112 };
selectionSort(a);
System.out.println("比较次数:" + cpNum);
System.out.println("移动次数:" + swapNum);
for (int i : a) {
System.out.print(i + "--");
}
}
static int cpNum = 0;
static int swapNum = 0;
public static void selectionSort (int[] a){
int t;
for (int i = 0; i < a.length; i++) {
for (int j = i+1 ; j < a.length; j++) {
cpNum++;
if (a[i] > a[j]){
swapNum++;
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
}
};
}
5. 冒泡排序
介绍：
冒泡排序（Bubble Sort，台湾译为：泡沫排序或气泡排序）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
步骤：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
代码：
/**
* 冒泡排序
* key 相邻
* 跌带出最大的数放到最后
* @author stephen
*
*/
public class BubbleSort {
/**
* @param args
*/
public static void main(String[] args) {
//int[] a = {1,2,3,4,5};
int[] a = {5,44,3,64,3,64,34,45,4,112};
//sort(a);
sortImproved(a);
System.out.println("比较次数:"+n);
for (int i : a) {
System.out.print(i+"--");
}
}
static int n = 0;
//C(n) = n(n-1)/2 Sworst(n) = n(n-1)/2 -- O(n^2)
public static void sort(int[] a){
int t;
for (int i = a.length-1; i >0; i--) {
for (int j = 0; j <i ; j++) {
if (a[j] > a[j+1])
{
t = a[j+1];
a[j+1] = a[j];
a[j] = t;
}
n++;
}
}
}
//Cmin(n) = n-1 Sworst(n) = n(n-1)/2 -- O(n^2)
public static void sortImproved(int[] a){
int t;
for (int i = a.length-1; i >0; i--) {
boolean isSwap = false;
for (int j = 0; j <i ; j++) {
if (a[j] > a[j+1])
{
t = a[j+1];
a[j+1] = a[j];
a[j] = t;
isSwap = true;
}
n++; //计算次数
}
if (!isSwap)
return;
}
}
}
6. 插入排序
介绍：
插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
步骤：
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置中
- 重复步骤2
代码：
/**
* Cworst(n) = (n-1)n/2 : O(n^2) Cavg = (n^2)/4 : O(n^2)
*
* @author stephenluu
*
*/
public class InsertionSort {
public static void main(String[] args) {
// int[] a = {5,4,3,2,1};
int[] a = { 5, 44, 9, 64, 3, 64, 34, 45, 3, 112 };
insertionSort(a);
System.out.println("比较次数:" + cpNum);
for (int i : a) {
System.out.print(i + "--");
}
}
static int cpNum = 0;
public static void insertionSort(int[] a) {
int t;
int j;
for (int i = 1; i < a.length; i++) {
t = a[i];
j = i - 1;
while (j >= 0 && a[j] > t) {
cpNum++;
a[j + 1] = a[j];
j--;
}
a[j + 1] = t;
}
}
}
7. 希尔排序
介绍：
希尔排序，也称递减增量排序算法，是插入排序的一种高速的改进版本。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
1、插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率
2、但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位>
代码：
这是D.Shell 的实现版本，不是我写的
int shellsortSh(int p[], int n) {
int op = 0;
int h, i, j, temp;
for (h = n / 2; h > 0; h = h / 2) {
for (i = h; i < n; i++) {
temp = p[i];
for (j = i - h; j >= 0 && p[j] > temp; j -= h) {
p[j + h] = p[j];
op++;
}
p[j + h] = temp;
op++;
}
}
return op;
}
分享到：
相关推荐
常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结
### 常用排序算法总结 #### 一、冒泡排序 冒泡排序是一种简单的排序算法，它重复地遍历待排序的数列，依次比较相邻的两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复进行的，直到没有再需要...
常用排序算法总结 数据结构 ppt 课件知识 排序的复杂性 。
### 数据结构中几种常用的排序算法总结 #### 一、引言 在计算机科学与数学领域，排序算法是一种能够按照特定顺序（如数值顺序或字典顺序）排列一系列数据的算法。排序算法对于许多其他算法（如搜索算法和合并算法）...
本文将对几种常见的内部排序算法和外部排序算法进行详细总结。 首先，排序的基本定义是：给定一个包含n个记录的序列，其关键字序列分别为K1, K2, ..., Kn，如果存在一个排列p1, p2, p3, ..., pn，使得关键字满足非...
### 几种内部排序算法总结 #### 冒泡排序（Bubble Sort） 冒泡排序是一种简单的排序算法，它重复地遍历待排序的数列，依次比较相邻的两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行的，...
快速排序是最常用的排序算法之一，由C.A.R. Hoare提出。它采用分治策略，选取一个“基准”元素，将数组分为两部分，使得一部分所有元素小于基准，另一部分所有元素大于基准，然后递归地对两部分进行快速排序。平均...
冒泡排序和快速排序是两种基础但广泛使用的数据排序算法。冒泡排序由于其简单直观的特性，易于理解和实现，而快速排序则以其较高的效率在数据量较大时展现出优势。 首先，让我们来看冒泡排序算法。冒泡排序通过重复...
本文将深入探讨四种常见的排序算法：直接插入排序、折半插入排序、冒泡排序和快速排序，并提供相应的C语言源代码实现。 1. 直接插入排序： 直接插入排序是一种简单直观的排序算法，它的工作原理类似于打扑克牌时的...
一、问题描述 本项目旨在实现并比较六...总结，这个项目提供了对C语言实现的排序算法的深入理解和实践，通过对各种排序方法的性能测试，我们可以更好地理解它们在不同场景下的适用性，并为实际问题选择合适的排序算法。
本文将对几种常见的排序算法进行详细的解析，包括冒泡排序、交换排序、选择排序和插入排序，这些都是在面试、笔试和学习过程中常遇到的基本排序方法。 1. **冒泡排序**： 冒泡排序是一种直观且基础的排序算法，...
本文主要总结和比较了九种常见的排序算法：快速排序、归并排序、堆排序、Shell排序、插入排序、冒泡排序、交换排序、选择排序以及基数排序。 1. **快速排序**：快速排序是一种基于分治思想的高效排序算法，由C.A.R....
### 常用排序算法的比较 #### 引言 排序是计算机科学中一项非常重要的基本操作，它涉及将一组数据元素（或记录）按照特定的顺序（通常是递增或递减）重新排列。排序的目的通常是为了提高后续操作如搜索等的效率。...
常用排序算法总结，包括插入排序(InsertionSort)，冒泡排序(BubbleSort)，选择排序(SelectionSort)，快速排序（QuickSort)， * 二路归并排序(MergeSort)，堆排序(HeapSort)。有每一种排序算法的复杂度分析以及实现...
总结来说，了解和掌握这些基本排序算法有助于开发者根据具体需求选择合适的排序方法，无论是为了优化性能还是为了理解算法的内在逻辑。在实际编程中，可以根据数据规模、是否已经部分排序等因素来选择使用冒泡排序、...