本文介绍六大常用算法的基本思路,以及相应的java函数实现。
本文的eclipse工程源代码可到以下链接下载:
http://download.csdn.net/detail/nostandby/9639511

下面将按照以下顺序进行介绍:
1、冒泡排序、冒泡排序的两种改进。
2、插入排序。
3、选择排序。
4、希尔排序。
5、归并排序。
6、快速排序。

1、冒泡排序:
相邻两个元素进行比较,如果反序就交换

	public void bubbleSort1(List<Integer> nums) {
		for (int i = nums.size(); i > 0; i--) {
			for (int j = 0; j < i - 1; j++) {
				if (nums.get(j).intValue() > nums.get(j + 1).intValue()) {
					swap(nums, j, j + 1);
				}
			}
		}
	}

冒泡排序改进1:
如果某一轮排序过程中没有发生交换,说明所有数据都已经有序,排序可以停止。

	public void bubbleSort2(List<Integer> nums) {
		boolean continueflag = true;
		for (int i = nums.size(); continueflag && i > 0; i--) {
			continueflag = false;
			for (int j = 0; j < i - 1; j++) {
				if (nums.get(j).intValue() > nums.get(j + 1).intValue()) {
					swap(nums, j, j + 1);
					continueflag = true;
				}
			}
		}
	}

冒泡排序改进2:
在改进1的基础上,记录每一轮停止时的索引,这个索引表明:该索引之后的元素都已排好。
那么下一轮到这一位置停止即可

	public void bubbleSort3(List<Integer> nums) {
		int flag;
		for (int i = nums.size(); i > 0; i = flag) {
			flag = 0;
			for (int j = 0; j < i - 1; j++) {
				if (nums.get(j).intValue() > nums.get(j + 1).intValue()) {
					swap(nums, j, j + 1);
					flag = j + 1;
				}
			}
		}
	}

2、插入排序
思想:将一个元素插入到一个有序序列中。
实现思路是:从索引为1 的位置遍历“数组”,将每个元素插入到它前面的有序序列中。
理解它的关键在于:待插入元素之前的元素都是有序的。

	public void insertionSort(List<Integer> nums) {
		int length = nums.size();
		for (int i = 1; i < length; i++) {
			for (int j = i; j > 0 && nums.get(j - 1).intValue() > nums.get(j).intValue(); j--) {
				swap(nums, j, j - 1);
			}
		}
	}

3、选择排序
思想:
(1)、从待排序列中先找到最小的元素,放到第一个位置。
(2)、再从剩余元素中找最小的,放到第二个位置。……
(3)、以此类推,直到所有元素都找到了自己的位置。
选择排序是固定位置,找元素;冒泡排序和插入排序是固定元素找位置。

	public void selectionSort(List<Integer> nums) {
		for (int i = 0; i < nums.size(); i++) {
			int lowindex = i;
			for (int j = i + 1; j < nums.size(); j++) {
				if (nums.get(j).intValue() < nums.get(lowindex).intValue()) {
					lowindex = j;
				}
			}
			swap(nums, i, lowindex);
		}
	}

4、希尔排序(缩小增量排序)
可以认为是插入排序的一种变形。
思路:
先将整个待排元素序列分割成若干子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序
然后依次缩减增量再进行排序
待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序(增量为1)。
其时间复杂度为O(n3/2),要好于直接插入排序的O(n2)

	public void shellSort(List<Integer> nums) {
		int length = nums.size();
		for (int i = length / 2; i > 2; i /= 2) {
			for (int j = 0; j < i; j++) {
				inssort(nums, i);
			}
		}
		inssort(nums, 1);
	}

	private void inssort(List<Integer> nums, int incr) {
		for (int i = incr; i < nums.size(); i += incr) {
			for (int j = i; j >= incr && nums.get(j - incr).intValue() > nums.get(j).intValue(); j -= incr) {
				swap(nums, j, j - incr);
			}
		}
	}

5、归并排序
分而治之,之后合并

	public void mergeSort(List<Integer> nums) {
		mergeSort(nums, 0, nums.size() - 1);
	}

	public void mergeSort(List<Integer> nums, int start, int end) {
		if (start == end)
			return;
		int mid = (start + end) / 2;
		mergeSort(nums, start, mid);
		mergeSort(nums, mid + 1, end);
		List<Integer> temp = new LinkedList<Integer>();
		for (int i = start; i <= end; i++) {
			temp.add(new Integer(nums.get(i).intValue()));
		}
		int i1 = 0, i2 = mid - start + 1;
		for (int curr = start; curr <= end; curr++) {
			if (i1 == mid + 1)
				nums.set(curr, temp.get(i2++));
			else {
				if (i2 > end - start)
					nums.set(curr, temp.get(i1++));
				else {
					if (temp.get(i1).intValue() < temp.get(i2).intValue())
						nums.set(curr, temp.get(i1++));
					else
						nums.set(curr, temp.get(i2++));
				}
			}
		}
	}

6、快速排序
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。时间复杂度为O(nlogn)

	public void qsort(List<Integer> nums) {
		qsort(nums, 0, nums.size() - 1);
	}

	public void qsort(List<Integer> nums, int start, int end) {
		if (start > end)
			return;
		int q = partition(nums, start, end);
		qsort(nums, start, q - 1);
		qsort(nums, q + 1, end);
	}

	private int partition(List<Integer> nums, int start, int end) {
		int keyIndex = end;
		int left = start, right = end - 1;
		while (left < right) {
			while (left < right && nums.get(left).intValue() < nums.get(keyIndex).intValue())
				left++;
			while (left < right && nums.get(right).intValue() > nums.get(keyIndex).intValue())
				right--;
			swap(nums, left, right);
		}
		swap(nums, left, keyIndex);
		return left;
	}

关于堆排序,桶排序,计数排序,基数排序等其他排序,时间问题,笔者目前还没有写出源代码。

以上内容仅代表笔者个人理解。如有错误欢迎交流指正。

参考资料:
1、《数据结构与算法分析(C++版)》
2、《算法导论》
3、http://www.open-open.com/lib/view/open1420372620468.html