全部博文(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)位置,不断的调整直至遍历完整个堆。