全部博文（118）
分类：
2009-09-02 23:30:23
排序的关键字
时间复杂度：整个排序算法运行所需要的时间。
空间复杂度：排序算法运行过程汇总所需要额外空间
稳定性：若待排的序列中有大小相同的两个数，若整个排序过程中不存在两数次序交换的可能新内阁，则该排序算法是稳定的。
in-place：算法使用的额外存储空间是常数级的。
由简入难，第一篇介绍最基本的冒泡排序——Bubble Sort。
public void swap(int[] data, int i, int j) { if (i != j) { data[i] = data[i] + data[j]; data[j] = data[i] - data[j]; data[i] = data[i] - data[j]; } }
冒泡排序，是所有排序中最简单的一种，也是效率最低的一种，时间复杂度O(n2)，空间复杂度O(n)。冒泡排序没有改变原始元素的相对位置，因此是稳定的排序。
冒泡排序动画：
冒泡排序java代码（递增）：
public void bubble_sort(int[] data) { for (int i = 0; i < data.length; i++) { for (int j = 0; j < data.length; j++) { if (data[j] > data[j + 1]) { swap(data, j, j + 1); } } } }
插入排序也是一种比较简单的排序方法，它的基本原理就好似我们打牌过程中摸牌理牌那一环，当你摸到一张牌后将其插入到合适的位置。
插入排序首先定位一个数（一般从第二个开始），将这个数依次与位于它之前的数进行比较，经过一轮比较，找到它在这些数中适当的位置。然后定位下一个数，再找到合适的为止，依次进行直到最后一个数。
例如（5 2 1 4 3），黑体为进行交换的两数。
第一轮：
（2 5 1 4 3）
第二轮：
（2 1 5 4 3）
（1 2 5 4 3）
第三轮：
（1 2 4 5 3）
（1 2 4 5 3）
（1 2 4 5 3）
第四轮：
（1 2 4 3 5）
（1 2 3 4 5）
（1 2 3 4 5）
（1 2 3 4 5）排序完成
排序插入在数据集较大的时候效率会变得恨低，但是它易于实现，处理小型数据集时效率较高，同时也是稳定的，in-place的，它的时间复杂度是O(n2)，空间复杂度是O(n)。
插入排序的动画：
插入排序的代码（递增）：
public void insertion_sort(int[] data) { int key = 0; int j = 0; for (int i = 1; i < data.length; i++) { key = data[i]; j = i - 1; while (j >= 0 && data[j] > key) { swap(data, j, j + 1); j = j - 1; } } }
选择排序的工作原理
找到数据集中的最小元素
将最小元素与未排序声誉元素的第一个元素交换
对剩余元素进行以上步骤
它的时间复杂度是O(n2)，空间复杂度是O(n)，同插入排序类似，它也不适用于大数据集。但是它易于实现，也是一种in-place的排序算法。对于稳定性：简易实现是不稳定的，例如（3 5 5 2），在第二轮中第二个五会被认为是最小的，然后同第一个五进行交换。
选择排序的动画：
选择排序代码（递增）：
public void selection_sort(int[] data) { int minimum = 0; for (int i = 0; i < data.length - 1; i++) { minimum = i; for (int j = i + 1; j < data.length; j++) { if (data[j] < data[minimum]) { minimum = j; } } swap(data, i, minimum); } }
public int ELFHash(String str, int number) {
int hash = 0;
long x = 0L;
char[] array = str.toCharArray();
for (int i = 0; i < array.length; i++) {
hash = (hash << 4) + array[i];
if ((x = (hash & 0xF0000000L)) != 0) {
hash ^= (x >> 24);
hash &= ~x;
}
}
int result = (hash & 0x7FFFFFFF) % number;
return result;
}
快速排序的步骤：
从数组中选出一个中枢数（pivot）
重新排列该数组，让数组中比该数小的数都排在该数的前面，比该数大的数都排在该数的后面。经过这次排序，该数处于其最终为止，并将原数组分为两个子数组（大于它的数组和小于它的数组），这就是分段的过程。
递归的排列各个子数组，直至最后整个数组排序完成。
快速排序的平均时间复杂度为O(nlogn)，空间复杂度依据各种实现方式有所不同。
快速排序的动画：
快速排序代码——partition：
public int partition(int[] data, int left, int right, int pivotIndex) { int privotValue = data[pivotIndex]; swap(data, pivotIndex, right); // Move pivot to end int storeIndex = left; for (int i = left; i < right; i++) { if (data[i] <= privotValue) { swap(data, i, storeIndex); storeIndex = storeIndex + 1; } } swap(data, storeIndex, right); // Move pivot to its final place return storeIndex; }
quickSort：
public void quick_sort(int[] data, int left, int right) { if (right > left) { int pivotIndex = left; int pivotNewIndex = partition(data, left, right, pivotIndex); quick_sort(data, index, pivotNewIndex - 1); quick_sort(data, pivotNewIndex + 1, right); } }
归并排序是一种基于比较的排序算法，在多数的实现方法中它是稳定的。归并排序可是由计算机祖师级人物——冯诺依曼提出的哦。
归并排序的过程：
如果数据链表的长度为0或1，则返回
将原始数据链表对半分成两个子链表
对每个子链表递归的调用合并排序进行排序
合并两个子链表使其成为一个排序完成的链表
归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。
归并排序的动画：
归并排序代码——mergesort：
public Listmergesort(List data) { if (data.size() <= 1) { return data; } int middle = data.size() / 2; List left = new ArrayList (); List right = new ArrayList (); for (int i = 0; i < middle; i++) { left.add(data.get(i)); } for (int i = middle; i < data.size(); i++) { right.add(data.get(i)); } left = mergesort(left); right = mergesort(right); List result = merge(left, right); return result; }
merge：
public Listmerge(List left, List right) { List result = new ArrayList (); while (left.size() > 0 && right.size() > 0) { if (((Integer)left.get(0)).intValue() <= ((Integer)right.get(0)).intValue()) { result.add(left.get(0)); left.remove(0); } else { result.add(right.get(0)); right.remove(0); } } if (left.size() > 0) { for (Iterator iter = left.iterator(); iter.hasNext();) { result.add(iter.next()); } } if (right.size() > 0) { for (Iterator iter = right.iterator(); iter.hasNext();) { result.add(iter.next()); } } return result; }
归并排序的示意图：
由以上示意图可以看出mergesort的过程很简单，白话一点就是：拆分拆分直至每个链表中仅有一个元素，合并合并合并至最终排好序的链表。merge是核心，经过递归调用归并排序后产生的left与right是已经排好序的两个子链表，依次比较left与right中的两数，将其放入适当的位置，然后删除子链表中已经放入result的那个数，最后将left和right中剩余的数依次放入result。问题：在实现的算法中，每次都要产生很多临时的list，这样效率是不是不高？
另曾经去一家小公司面试，工程师出了一道题：给定两个排好序的数组，如何将其合并成新的数组依然有序，似乎就是归并排序的应用，我的答案：
public int[] merge(int[] left, int[] right) { int result[] = new int[left.length + right.length]; int index = 0; // index of result int x = 0; // index of left int y = 0; // index of right // compare each element in two arrays, after comparing, index++ while (x < left.length && y < right.length) { if (left[x] < right[y]) { result[index++] = left[x++]; } else { result[idnex++] = right[y++]; } // the length of two arrays might be different, // so we have to copy the rest elements in two arrays while (x < left.length) { result[index++] = left[x++]; } while (y < right.length) { result[index++] = right[y++]; } return result; } }
代码的思想：将两个数组中的每一个数组经过比较填入结果数组，由于可能两个数组的长度不等，最后还要将那个数组中剩余的数值填入结果数组。
堆排序是一种基于比较的排序算法，它比实现的较好的快速排序慢一些，但是它的平均时间复杂度为O(nlogn)，空间复杂度为O(n)，它是一种in-place的算法，但是确实不稳定的排序算法。
最大堆和最小堆的定义：
根结点（亦称为堆顶）的关键字是堆里所有节点关键字中最小者的堆成为最小堆。
根结点（亦称为堆顶）的关键字是堆里所有节点关键字中最大者的堆成为最大堆。
P.S.:
堆中任一子树亦是堆。本文讨论的堆实际上是二插堆（Binary Heap），类似地可以定义k叉堆。
堆排序的过程：
根据输入的数据集建立一个最大堆（最小堆）
进行堆排序，将Root（最大值）与堆的最后一个元素交换
堆调整，继续维护成为最大堆
进行步骤2和3，直至排序完成
堆排序动画：
堆排序代码——siftDown：
public void siftDown(int[] data, int start, int end) { int root = start; while ((2 * root + 1) <= end) { int child = root * 2 + 1; int (child < end && data[child] < data[child + 1]) { child++; } if (data[root] < data[child]) { swap(data, root, child); root = child; } else { break; } } }
这段代码是堆排序的核心，对堆中的元素进行调整。简单来说做的工作就是，即针对一个堆点，将其与它孩子中较大的那个进行比较，若大不变，若小与该孩子交换位置，若交换后该堆点（处于原先它孩子的位置）仍有孩子则继续与孩子中较大的那个进行比较，若大不变，若下与该孩子交换位置，调整直至该堆点没有孩子结束。
heapify:
public void heapify(int[] data, int count) { int start = (count - 1) /2; while (start >= 0) { siftDown(data, start, count - 1); start = start - 1; } }
这段代码是建堆的过程，找到最后一个有孩子的堆点，对该堆点进行调整，直至调整到Root。
heapsort:
public void heapsort(int[] data, int count) { heapify(data, count); int end = count - 1; while (end > 0) { swap(data, 0, end); siftDown(data, 0, --end); } }
这段代码解释了堆排序的过程，首先建堆，然后将Root与堆底元素交换，继而调整现有堆中Root（交换后的Root）位置，不断的调整直至遍历完整个堆。