重拾算法，从基本写起。我觉得在算法中除了作为基础的数据结构，基本中的基本就是排序。
闲话不多说，我想分析的排序包括以下几种：鸡尾酒排序(双向冒泡)、快速排序、归并排序、堆排序、基数排序。
1.鸡尾酒排序
嘿嘿，这个排序名字很好听，其实是在这几种排序中最简单的，当然效率显然也是低下的。思想是这样的，首先是0—n，选出最小的放在第0号位置，最大的放在n号位置，接着对1—(n-1)执行同样地操作。当i>j了终止（i是起始位置，j是终止位置）。平均时间复杂度为O(n2)，虽然这个时间复杂度和冒泡一样，但显而易见，与冒泡相比，访问原序列的次数大大减少了。以下是Java版代码
public class CocktailSort {
public void cocktailSort(int[] data) {
int sta = 0;
int i;
int end = data.length - 1;
while (sta < end) {
for (i = sta; i < end; i++) {
if (data[i] > data[i + 1]) {
int t = data[i];
data[i] = data[i + 1];
data[i + 1] = t;
}
}
end--;
for (i = end; i > sta; i--) {
if (data[i] < data[i - 1]) {
int t = data[i];
data[i] = data[i - 1];
data[i - 1] = t;
}
}
sta++;
}
}
}
当然这里可以在比较中记录最大和最小的索引，实现在循环一次交换但其实是一个性质，这里不加以优化。
2.快速排序
学计算机的同学肯定都懂的。快排作为学数据结构必须掌握的算法之一，有着良好的性能。在这里我列出的几种排序中，快排是排序中平均速度最快的，但简单的快排是不稳定的，所以在特殊情况下可能和冒泡近似。来说说快排的原理：
选用了百度中的一张截图作为指针移动示例，快排中最重要的就是两个指针（在Java中可以说是两个索引）的移动和与Key值得交换，指针分别为头指针和尾指针，Key值为比较值，一趟快排的目的是确定Key所在的位置，并且使Key之前的数均小于Key，之后的数均大于Key。初始化时，Key值一般设为第一个数（这时头指针指向Key值），尾指针指向末尾（示例中Key为49，头指针指向49，尾指针指向27）。这时从尾指针开始向前，一个个比较，当指向值小于Key值时，将Key值与该值交换，然后头指针开始向后移动，当该值大于Key值是交换，然后尾指针继续移动，这样循环直到头尾指针指向同一个位置，此时一趟排序结束，接下去就很简单，调用递归，对Key的前半部分和后半部分分别进行快排。示例中，一趟快排的结果为：
27 38 13 49 76 97 65
在写代码时，要注意的是，Key的位置最后肯定在头尾指针重合处，所以在之前交换的时候，只需将需要交换的值赋给Key值所在的位置，而不用实质意义上的交换。个人觉得快排很好很强大。
import java.util.Random;
public class Qsort {
/**
* 快速排序
* @param i：起始位置（包含）
* @param j：末位置（包含）
* @param data：需要排序的数组
*/
public void qSort(int i, int j, int[] data) {
int st = i;//头指针
int ed = j;//尾指针
if (i < j) {
int id=(int)(Math.random()*(j-i))+i;
int key=data[id];
data[id]=data[st];
data[st]=key;
while (st < ed) {
while (data[ed] >= key && st < ed)
ed--;
data[st] = data[ed];
while (data[st] <= key && st < ed)
st++;
data[ed] = data[st];
}
data[ed] = key;
qSort(i, ed - 1, data);
qSort(ed + 1, j, data);
}
}
}
可以看到在写快排的时候我用到了随机数，这是为了防止当出现倒序的时候使快排褪变为冒泡而采取的优化，即随机取一个范围内的索引与起始位置交换并作为Key值。当然这种快排在出现许多重复值时仍会出现极端情况,快排的平均时间复杂度为nlogn。
3.堆排序
说到堆排序，首先先说说最小、大堆。以最大堆为例，最大堆是一种二叉堆，从实现上来说的说就是一棵完全二叉树，其中任意一个子堆或者说子树中根节点均大于两个子节点，所以整棵树的根节点为这棵树的最大值。而完全二叉树的存储方式就可以用数组来实现了。用数组模拟完全二叉树，假如在数组中的索引为n，那么这个结点在二叉树中的子节点在数组中的索引分别为(2n+1)和(2n+2)(很巧妙啊)。那怎么样来建堆呢？这就是仁者见仁智者见智了，比如插入法等。我这里采用的是一种比较简单的方法，从小到大，自上而下，是每个子堆都为一个最大堆，并且需要调整时，从子堆根结点开始向下调整。以途中二叉树为例讲解：
首先需要找到最后一个拥有子节点的根节点，即n/2（数组中索引是(n-1)/2），这个根节点所在的堆是最小并且最靠后的子堆，然后从这个结点向左走（走到最左边就跳到上一层最右边继续），每走到一个点就把那个结点作为根的树变为最大堆，具体操作就是如果根比左右子节点中较大的那个节点小，则与之交换，并且继续向下走直到走到叶节点位置。图中，先12与6交换，然后当走到3时，3的两个子节点分别为12和7，与12交换，然后再与6交换（6为叶节点）。学会了建最大堆，那就简单了，对一个长度为n的数组排序，首先对0—（n-1）调整，然后把0与（n-1）交换，然后对0—（n-2）调整，再交换，每次都把最大的数往后抛，堆排序就完成了！！！(不知道看懂了没。。。)
public class HeapSort {
/**
* 调整子堆
* @param i:起始位置
* @param j：终止位置
* @param data：需要排序的数组
*/
public void AdjustHeap(int s,int e,int[] data)
{
for(int i=s*2+1;i<e;i=i*2+1)
{
if(data[i]<data[i+1])
{
i=i+1;
}
if(data[s]>=data[i])
break;
else
{
int t=data[i];
data[i]=data[s];
data[s]=t;
}
s=i;
}
}
public void heapSort(int[] data)
{
int n=data.length-1;
for(int i=(n-1)/2;i>=0;i--)//第一次建堆
{
AdjustHeap(i,n, data);
}
for(int i=data.length-1;i>=0;i--)
{
int t=data[0];
data[0]=data[i];
data[i]=t;
AdjustHeap(0, i-1, data);
}
}
}
代码中又可以优化的地方，比如在第一次建堆后调整时，只需要直接从根结点向下走一遍即可。
堆排序的时间复杂度为nlogn,而且是一种相对稳定的排序算法，这在后面的比较中可以明显看到。
4.归并排序
比较容易理解的一种排序，这里特指二路归并，就是把数组分成两份（等分），把两份头排好序后就合并，按照思路比较好的方法就是递归的思想（当然非递归也是可以的）。主要的优化是在合并的时候。分别用两个数记录两段数组的起始位置，然后比较，小的那个数插入到一个临时数组中，然后小的数的索引向后走，直到把其中一段数组走完，剩下就是把没走完的那一段数组直接放在临时数组的最后一段，这样就排好序了。显而易见的缺点就是需要一个多余的数组空间。时间复杂度上来讲是nlogn，也是一种稳定的排序，并且按理论上来说在大数组时应该快于堆排序（测试中好像不是这样。。。）
public class MergeSort {
int[] temp;
/**
*
* @param len:数组长度
*/
public MergeSort(int len) {
// TODO Auto-generated constructor stub
temp=new int[len];
}
/**
* 进行归并
*
* @param data
* ：数组
* @param st
* ：前半部分
* @param mid
* ：分界
* @param end
* ：后半部分
*/
public void merSort(int[] data, int st, int mid, int end) {
int k = st;
int i = st;
int j = mid + 1;
for (; i < mid + 1 && j <= end; k++) {
if (data[i] <= data[j]) {
temp[k] = data[i];
i++;
} else {
temp[k] = data[j];
j++;
}
}
for (; i < mid + 1; i++,k++)
temp[k] = data[i];
for (; j < end + 1; j++,k++)
temp[k] = data[j];
for (i =st; i < end+1; i++)
data[i] = temp[i];
}
/**
* 对数组的st到end进行排序
*
* @param data
* ：需要排序的数组
* @param st
* ：排序的起始位置
* @param end
* :排序的末位置
*/
public void sortHelp(int[] data, int st, int end) {
int mid = (st + end) / 2;
if (st<end) {
sortHelp(data, st, mid);
sortHelp(data, mid + 1, end);
merSort(data, st, mid, end);
}
else
return;
}
}
为了减少空间的浪费，我就定义了一个temp数组，让排序在temp中进行部分调整。
5.基数排序
说白了就是根据键值的大小进行排序。比如n个整数，最大的为三位数，那么百位大的数肯定最大，十位大的其次，个位相对最不重要。所以简单的基数排序分为这么几步（采用最低键值LDS）：一、计算数组中的最高位（整数的话就是长度） 二、建立一个长度为10的链表数组，从键值最轻的开始（个位），根据个位数的值，分别放入相应数组中的链表中 三、收集。对数组中的数，从数组的索引0-9进行收集，成为一个新的序列，这是一趟基数排序完成。四、重复二、三步骤，其中键值依次增重，（即个位，然后十位，百位.....）。时间复杂度为O (nlog(r)m），当然也是一种稳定的排序。
import java.util.ArrayDeque;
public class RadixSort {
/**
* 基数排序
*
* @param data
* ：对象数组
* @param len
* :数据最高位数
*/
public void radixSort(int[] data, int len) {
int size = data.length;
int radix = 1;
ArrayDeque<Integer>[] li = new ArrayDeque[10];
for (int i = 1; i <= len; i++) {
// 分配
for (int j = 0; j < size; j++) {
int index = (data[j] / radix) % 10;
if (li[index] == (null))
li[index] = new ArrayDeque<Integer>();
li[index].add(data[j]);
}
int k = 0;
for (int j = 0; j < 10; j++) {
ArrayDeque<Integer> ab = li[j];
if (ab != null) {
while(!ab.isEmpty()){
data[k] = ab.pollFirst();
k++;}
ab.clear();
}
}
radix = radix * 10;
}
}
}
呵呵，看了这个代码，高手肯定想吐血，不过，对于这个排序我只是想说明他在重复值较多的时候的高效性，所以即使采用了库中的类（链表队列），性能还是很好区分的。
6.测试
写完了这几种排序后，对这种排序进行了一个测试，不包括鸡尾酒排序（双向冒泡还是太慢了），测试类如下
import java.util.Arrays;
import java.util.Date;
import java.util.Random;
public class Test {
public static void main(String[] args) {
Random ran = new Random();
int num = 1000000;
int[] data = new int[1000000];
int[] data1 = new int[1000000];
int[] data2 = new int[1000000];
int[] data3 = new int[1000000];
int[] data4 = new int[1000000];
int[] data5 = new int[1000000];
int biglen=0;
for (int i = 0; i < num; i++) {
data[i] =ran.nextInt(10000)+1;
if(biglen<String.valueOf(data[i]).length());
biglen=String.valueOf(data[i]).length();
data1[i] = data[i];
data2[i] = data[i];
data3[i] = data[i];
data4[i] = data[i];
data5[i] = data[i];
}
System.out.println("输入完毕"+biglen);
data1 = data;
int len=data3.length;
Qsort qsort = new Qsort();
HeapSort hsort = new HeapSort();
MergeSort msort=new MergeSort(len);
//CocktailSort csort=new CocktailSort();
RadixSort rsort=new RadixSort();
Date da = new Date();
long a = da.getTime();
qsort.qSort(0, data1.length - 1, data1);
da = new Date();
long b = da.getTime();
System.out.println("快速排序 time=" + (b - a));
da = new Date();
a = da.getTime();
hsort.heapSort(data);
da = new Date();
b = da.getTime();
System.out.println("堆排序 time=" + (b - a));
da = new Date();
a = da.getTime();
Arrays.sort(data2);
da = new Date();
b = da.getTime();
System.out.println("系统排序 time=" + (b - a));
da = new Date();
a = da.getTime();
msort.sortHelp(data3, 0, len-1);
da = new Date();
b = da.getTime();
System.out.println("归并排序 time=" + (b - a));
da = new Date();
a = da.getTime();
rsort.radixSort(data5, biglen);
da = new Date();
b = da.getTime();
System.out.println("基数排序 time=" + (b - a));
}
}
第一次采用随机数，数据量为1000000，数据在0-10000，结果如下：
系统排序指的是Arrays.sort()，比较下可以发现相对而言堆排序时间比较快。
第二次采用倒序的序列，数据量为1000000，结果如下：
- 大小: 3.8 KB
- 大小: 9 KB
- 大小: 2.2 KB
分享到：
相关推荐
数据结构各种排序算法实现及比较 在本文中，我们将讨论各种排序算法的实现和比较，包括简单选择排序、直接插入排序、希尔排序、冒泡排序、快速排序等。这些算法都是数据结构课程设计报告中常用的排序算法。 简单...
【内部排序算法的比较分析与实现】 内部排序是计算机科学中数据处理的重要组成部分，它涉及到如何有效地对一组数据进行排序，以达到特定的顺序。在本文中，作者李镜子使用C语言设计并实现了一个测试程序，目的是...
本篇我们将讨论如何使用Java实现拓扑排序，并对其进行深入的分析。 首先，我们来了解拓扑排序的基本步骤： 1. **寻找入度为0的节点**：入度是指指向一个节点的边的数量。在有向无环图中，入度为0的节点没有前驱，...
`Algorithm.java`文件可能包含了这些排序算法的Java实现代码，而`常见排序算法的实现与性能比较.doc`文档则可能详细比较了这些算法的性能和适用场景。`readme.txt`文件可能是对整个项目的简要说明，包括如何运行和...
本文将探讨如何使用这两种语言实现几种基本的排序算法：冒泡排序、选择排序，以及两种全比较排序（并行和串行）。 首先，让我们了解一下排序算法。排序是计算机科学中最基础的操作之一，它涉及到将一组数据按照特定...
通过对这五种排序算法的比较和实践，我们可以更好地理解算法设计与分析的基本原则，这将为后续的编程和算法学习奠定坚实的基础。在实际应用中，了解这些基础排序算法的特性有助于我们做出明智的选择，为特定问题找到...
### 排序及基本算法详解 #### 一、排序的基本概念与分类 排序是一种常见的数据组织方式，旨在根据数据的某一属性（关键字）将其按升序或降序排列。这一过程不仅限于数字，也可以应用于字母、字符串或其他任何可...
1. **冒泡排序（Bubble Sort）**：冒泡排序是最简单的排序方法之一，它通过重复遍历待排序的元素列表，比较相邻元素并交换位置来实现排序。在这个项目中，可能会有实现冒泡排序的源文件，如`bubble_sort.cpp`，它...
##### 3.1 函数 `merge_sort_impl` 实现分析 ```c void merge_sort_impl(int* storage, int* array, int low, int mid, int high) { // ...代码省略... } ``` 此函数是归并排序的核心实现部分。参数说明如下： - ...
3． 掌握各种排序方法的优劣分析及花费的时间的计算。 4． 掌握各种排序方法所适应的不同场合。 此设计题目要求了解掌握各种排序算法、分析其优劣。故设计总体框架如下：定义一个主函数，在主函数中定义一个长度...
冒泡排序是一种简单的排序算法，它的基本思想是将相邻的元素进行比较和交换，以达到排序的目的。这种算法的时间复杂度为O(n^2)。在链表实现时，我们可以使用链表的指针来实现冒泡排序。 快速排序 快速排序是一种...
在IT领域，排序算法是计算机科学中的核心概念，特别是在数据结构和算法分析中。这里我们主要探讨的是五种不同的排序算法：插入排序、选择排序、快速排序、希尔排序以及冒泡排序，它们都有对应的链表实现。让我们逐一...
### 数据结构中各种排序算法的比较与分析 #### 排序的基本概念 排序是指按照一定的规则（例如数值大小、字母顺序等）对一组数据进行重新排列的过程。在计算机科学领域，排序是一种基本的操作，用于组织数据以便...
1. **基本排序算法**： - **冒泡排序**：通过重复遍历待排序的元素列表，比较相邻元素并交换顺序，使得每次遍历时最大（或最小）的元素逐渐“浮”到数组的一端。 - **选择排序**：每次从未排序的元素中找到最小...
### 排序算法实现及比较 #### 冒泡排序 - **原理**：通过重复地遍历列表，比较每对相邻项并交换顺序错误的项。 - **实现步骤**： - 遍历整个数组，比较相邻的元素。 - 如果第一个元素大于第二个元素，则交换它们...
根据给定文件的信息，本文将对五种内部排序算法...简单选择排序实现简单但效率较低；而快速排序和归并排序则适用于大规模数据集，且在实际应用中非常广泛。在选择排序算法时，应根据具体的应用场景和数据特点来决定。
"内部排序算法的实现与比较"这个主题涵盖了多种用于在内存中对数据进行排序的算法，这些算法在计算机软件技术基础的学习中占有重要地位。南航计算机软件技术基础课程通常会深入探讨这些概念，以便学生理解和掌握。 ...
本文章将对各种排序算法的原理、实现及其效率进行深入分析。 1. 直接插入排序 直接插入排序的基本原理是把数据集视为一个有序表和一个待插入的元素，将待插入元素插入到有序表中的适当位置，保持有序表的有序状态。...
根据提供的信息，我们可以总结出以下关于八种基本排序算法中的两种——冒泡排序（Bubble Sort）与插入排序（Insert Sort）的知识点。 ### 冒泡排序（Bubble Sort） #### 定义 冒泡排序是一种简单的排序算法。它...
选择排序是一种简单的排序算法，其基本思想是每次从未排序的元素中找出最小（或最大）的元素，将其放置到已排序序列的末尾。时间复杂度为O(n^2)，虽然简单易懂，但在处理大数据量时效率较低。 **2. 冒泡排序(Bubble...