舞动的排序算法快速排序

有感于这段来至Sapientia University 的舞蹈，生动有趣、寓教于乐，突然心血来潮，来一个看视频学排序吧。于是按照视频的步骤写了一个一样的快速排序算法。以前学过快排，只是觉得复杂，没有自己实现过，学得似懂非懂，今天看了这个视频，真让人印象深刻，真正把快速排序算法学懂了了，推荐学计算机的童鞋们都来看看。我很佩服这段舞蹈编排者的创意，把刚写的代码贴在下面留作纪念。

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n²)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来，且在大部分真实世界的数据，可以决定设计的选择，减少所需时间的二次方项之可能性。

参考百度百科 http://baike.baidu.com/view/19016.htm

下面的这段程序是我写的快速排序的java实现

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a = { 3, 0, 1, 8, 7, 2, 5, 4, 9, 6 };

		int i = 0;
		int j = a.length - 1;
		quicksort(a, i, j);

	}

	private static void quicksort(int[] a, int i, int j) {

		if (i < j) {
			int start = i;
			int end = j;
			int pivot = i;
			print(a, pivot);
			boolean b = true;
			while (i < j) {
				if (b) {

					if (a[j] < a[pivot]) {
						System.out.println("a[" + pivot + "] > a[" + j
								+ "]  swap!");
						swap(a, pivot, j);
						pivot = j;
						i++;
						print(a, pivot);
						b = false;
					} else {
						// System.out.println("a[" + pivot + "] < a[" + j
						// + "]  do nothing!");
						j--;
					}
				}
				if (b == false) {

					if (a[i] > a[pivot]) {
						System.out.println("a[" + i + "] > a[" + pivot
								+ "]  swap!");
						swap(a, pivot, i);
						pivot = i;
						j--;
						print(a, pivot);
						b = true;
					} else {
						// System.out.println("a[" + i + "] < a[" + pivot
						// + "]  do nothing!");
						i++;
					}
				}
			}

			quicksort(a, start, pivot - 1);

			quicksort(a, pivot + 1, end);
		}
	}

	private static void swap(int[] a, int i, int j) {
		int temp = a[j];
		a[j] = a[i];
		a[i] = temp;

	}

	private static void print(int[] a, int pivot) {
		for (int i = 0; i < a.length; i++) {

			System.out.print("a[" + i + "]" + ",");
		}
		System.out.println();
		System.out
				.println("---------------------------------------------------------");
		for (int i = 0; i < a.length; i++) {

			System.out.print("  " + a[i] + " ,");
		}
		System.out.println();
		System.out
				.println("=========================================================");
		System.out.println("    pivot : " + pivot);

	}

}

输出

a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9],
---------------------------------------------------------
  3 ,  0 ,  1 ,  8 ,  7 ,  2 ,  5 ,  4 ,  9 ,  6 ,
=========================================================
    pivot : 0
a[0] > a[5]  swap!
a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9],
---------------------------------------------------------
  2 ,  0 ,  1 ,  8 ,  7 ,  3 ,  5 ,  4 ,  9 ,  6 ,
=========================================================
    pivot : 5
a[3] > a[5]  swap!
a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9],
---------------------------------------------------------
  2 ,  0 ,  1 ,  3 ,  7 ,  8 ,  5 ,  4 ,  9 ,  6 ,
=========================================================
    pivot : 3
a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9],
---------------------------------------------------------
  2 ,  0 ,  1 ,  3 ,  7 ,  8 ,  5 ,  4 ,  9 ,  6 ,
=========================================================
    pivot : 0
a[0] > a[2]  swap!
a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9],
---------------------------------------------------------
  1 ,  0 ,  2 ,  3 ,  7 ,  8 ,  5 ,  4 ,  9 ,  6 ,
=========================================================
    pivot : 2
a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9],
---------------------------------------------------------
  1 ,  0 ,  2 ,  3 ,  7 ,  8 ,  5 ,  4 ,  9 ,  6 ,
=========================================================
    pivot : 0
a[0] > a[1]  swap!
a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9],
---------------------------------------------------------
  0 ,  1 ,  2 ,  3 ,  7 ,  8 ,  5 ,  4 ,  9 ,  6 ,
=========================================================
    pivot : 1
a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9],
---------------------------------------------------------
  0 ,  1 ,  2 ,  3 ,  7 ,  8 ,  5 ,  4 ,  9 ,  6 ,
=========================================================
    pivot : 4
a[4] > a[9]  swap!
a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9],
---------------------------------------------------------
  0 ,  1 ,  2 ,  3 ,  6 ,  8 ,  5 ,  4 ,  9 ,  7 ,
=========================================================
    pivot : 9
a[5] > a[9]  swap!
a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9],
---------------------------------------------------------
  0 ,  1 ,  2 ,  3 ,  6 ,  7 ,  5 ,  4 ,  9 ,  8 ,
=========================================================
    pivot : 5
a[5] > a[7]  swap!
a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9],
---------------------------------------------------------
  0 ,  1 ,  2 ,  3 ,  6 ,  4 ,  5 ,  7 ,  9 ,  8 ,
=========================================================
    pivot : 7
a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9],
---------------------------------------------------------
  0 ,  1 ,  2 ,  3 ,  6 ,  4 ,  5 ,  7 ,  9 ,  8 ,
=========================================================
    pivot : 4
a[4] > a[6]  swap!
a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9],
---------------------------------------------------------
  0 ,  1 ,  2 ,  3 ,  5 ,  4 ,  6 ,  7 ,  9 ,  8 ,
=========================================================
    pivot : 6
a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9],
---------------------------------------------------------
  0 ,  1 ,  2 ,  3 ,  5 ,  4 ,  6 ,  7 ,  9 ,  8 ,
=========================================================
    pivot : 4
a[4] > a[5]  swap!
a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9],
---------------------------------------------------------
  0 ,  1 ,  2 ,  3 ,  4 ,  5 ,  6 ,  7 ,  9 ,  8 ,
=========================================================
    pivot : 5
a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9],
---------------------------------------------------------
  0 ,  1 ,  2 ,  3 ,  4 ,  5 ,  6 ,  7 ,  9 ,  8 ,
=========================================================
    pivot : 8
a[8] > a[9]  swap!
a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9],
---------------------------------------------------------
  0 ,  1 ,  2 ,  3 ,  4 ,  5 ,  6 ,  7 ,  8 ,  9 ,
=========================================================
    pivot : 9

下面是其它经典排序算法介绍，还有同样来至Sapientia University 创作的舞蹈视频，他们以舞蹈的方式演绎各种排序算法，创意无限，非常精彩

冒泡排序 参考百度百科http://baike.baidu.com/view/254413.htm

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

视频：

http://v.youku.com/v_show/id_XMzMyOTAyMzQ0.html

希尔排序 参考百度百科http://baike.baidu.com/view/178698.htm

希尔排序（Shell Sort），也称递减增量排序算法，是插入排序的一种高速而稳定的改进版本。希尔排序是基于插入排序的以下两点性质而提出改进方法的：插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率,但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

视频：

http://v.youku.com/v_show/id_XMzMyODk5MzI4.html

选择排序 参考百度百科http://baike.baidu.com/view/547263.htm

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。

视频：

http://v.youku.com/v_show/id_XMzMyODk5MDI0.html

插入排序 参考百度百科http://baike.baidu.com/view/1193395.htm

插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

视频：

http://v.youku.com/v_show/id_XMjU4NTY5MzEy.html

归并排序 参考百度百科http://baike.baidu.com/view/90797.htm

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

视频：

http://v.youku.com/v_show/id_XMzMyODk5Njg4.html

这个网站上还有这些经典排序算法很不错的图形演示 http://jsdo.it/norahiko/oxIy/fullscreen

分享到：