排序算法
排序算法虽然目前考得不多了，因为大家面试都在准备，面试官喜欢反其道而行之。不过，不管考不考，掌握排序算法对我们来说是百利无一害的。
主要的排序算法如下：
- 冒泡排序
- 选择排序；
- 插入排序；
- 快速排序；
- 归并排序；
- 堆排序；
1、冒泡排序
思想：遍历元素，每一次从由往左每两个元素比较，如果前一个元素大于后一个元素，则交换两个元素，一次遍历之后，最小的元素升到最左边，上一次循环后的右边。
def maopao(array):
length = len(array)
for i in range(length):
j = length - 1
exchange = False
while j > i:
if array[j] < array[j-1]:
array[j],array[j-1] = array[j-1],array[j]
exchange = True
j -= 1
if not exchange :
break
array = [4,6,1,8,3,5,2]
maopao(array)
print array
JAVA版本：
public static int[] maopaoSort(int[] array){
if (array == null){
return null;
}
int len = array.length;
if (len == 1){
return array;
}
boolean flag = false;
for (int i = 0;i<len - 1;i++){
for (int j = len - 1;j>i;j--){
if (array[j] < array[j-1]){
int temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
flag = true;
}
}
printArr(array);
if (!flag) break;
}
return array;
}空间复杂度:很明显，不必多余空间,即O（1）；
时间复杂度：
1、最优情况：O(n)。最优的情况是已经排好序了。我设了一个标记为exchange，默认值是FALSE，那当我第一次遍历结束的时候，如果没有发生过交换，意味着该列表已经排好序了，就直接跳出循环。因为只遍历一次，时间复杂度是O(n)。
2、平均和最坏：O(n^2)。
稳定性：稳定。遇到相等元素，不需要交换。因此是稳定的。
2.快速排序
思路：采用分治的思想，选择一个基数，然后将数组分成两部分，比基数小的放在基数左边，比基数大的放在右边。然后再对每一个分数组进行分治，逐层递归。
def fsort(array):
return fsort([lt for lt in array[1:] if lt < array[0]]) + \
[array[0]] + \
fsort([gt for gt in array[1:] if gt >= array[0]]) \
if len(array)> 1 else array
print fsort(array)
Python的写法真的是超简洁。逐层递归，直到列表长度为1。
先说一下这种算法的最差，平均的情况。最差的情况是我每次递归分成的两个数组都是一个是全部，一个是空，比如我每次选择的基数都是当前的最小值，那左边的数组就是空，后边的是整个列表。这需要n次递归。
空间复杂度：
最优和平均：O(logn)
最坏：O(n)
时间复杂度：
- 最优和平均：O(nlogn)
- 最坏：O(n^2)
稳定性：不稳定啊
上面是通过递归实现的，下面再用非递归来实现一下：
思想：同样是上面思路，只不过不是创建临时数组，然后对子数组进行重新排序，而是通过栈的形式实现。每次都向栈中压入起始和终止位置。第一次压入列表的第一个和最后一个元素位置，然后通过第一次比对，把小的放在列表右边，大的放在列表左边，得到基准数的当前位置。然后再压入左边的坐标范围和右边的坐标范围，这样依次循环。代码：
class Stack(object):
def __init__(self,size):
self.size = size
self.stack = []
def push(self,value):
self.stack.append(value)
def pop(self):
return self.stack.pop(-1)
def isFull(self):
if len(self.stack) == self.size:
return True
return False
def isEmpty(self):
if len(self.stack) == 0:
return True
return False
def top(self):
return self.stack[-1]
def partation(array,start,end):
base = array[start]
index = start
while index < end:
while index < end and array[end] >= base:
end -= 1
#此时，end当前位置比base小，所以将左边的赋予end当前位置
array[index] = array[end]
while index < end and array[index] <= base:
index += 1
#此时，index当前位置比base大，所以就把end设置index的元素。
array[end] = array[index]
#循环结束后，index和end是相等的，这也是基准数的新位置。
array[index] = base
print array
return index
def qsort(array):
start, end = 0, len(array)-1
stack = Stack(len(array))
stack.push(start)
stack.push(end)
while not stack.isEmpty():
#在栈中
end = stack.pop()
start = stack.pop()
if start > end:
continue
#一是实现排序，二是得到基准数的位置
index = partation(array,start,end)
#将左边的两个坐标压入
if start < index-1:
stack.push(start)
stack.push(index-1)
#将右边的也压入栈。
if index+1 < end:
stack.push(index+1)
stack.push(end)
return array
print qsort([3, 1, 2, 5, 4, 2, 6])
JAVA版本：
public static int[] qsort2(int[] array){
int start = 0,end = array.length -1 ;
ArrayDeque<Integer> deque = new ArrayDeque<>();
deque.push(start);
deque.push(end);
doQsort2(array,deque);
return array;
}
private static void doQsort2(int[] array,ArrayDeque<Integer> deque){
while (!deque.isEmpty()){
Integer end = deque.pop();
Integer start = deque.pop();
System.out.println(start);
System.out.println(end);
if (start >= end) continue;
int pos = partationPos(array,start,end);
if (pos - 1 > start){
deque.push(start);
deque.push(pos - 1);
}
if (pos+1 < end){
deque.push(pos+1);
deque.push(end);
}
}
}
private static int partationPos(int[] array,int start,int end){
int baseValue = array[start];
int left = start ;
int right = end;
while (left<right){
while (right > left && array[right] >= baseValue) right -- ;
while (left < right && array[left] <= baseValue) left ++;
swap(array,left,right);
}
swap(array, start,right);
return right;
}3、选择排序
思路：对每一位置都选当前最小的元素，依次遍历到列表末尾
def selectsort(array):
for i in range(len(array)-1):
smallest = i
#print smallest
for j in range(i+1,len(array)):
if array[smallest] > array[j]:
smallest = j
if i != smallest:
array[i],array[smallest] = array[smallest],array[i]
selectsort(array)
print arrayJAVA：
public static int[] selectSort(int[] array){
if (array == null){
return null;
}
int len = array.length;
if (len == 1){
return array;
}
for (int i=0;i<len-1;i++){
int index = i;
int small = array[i];
for (int j=i+1;j<len;j++){
if (array[j] < small){
small = array[j];
index = j;
}
}
array[index] = array[i];
array[i] = small;
}
return array;
}时间复杂度：O(n^2)，无论最优还是最差，都要这个复杂度。
空间复杂度：O(1)
4、归并排序
思路：采用递归的思想，将列表拆成两个子列表，每个子列表再进行递归，出口是元素个数是1.对于两个子列表进行排序的规则是，创建一个临时列表，然后依次遍历两个列表进行比较，每次把两表中对应位置上较小的插入到临时数组中。
def merge(L1,L2):
temp = []
#sort L1 and L2,and store result to a temp list
while L1 and L2:
if L1[0] < L2[0]:
temp.append(L1.pop(0))
else:
temp.append(L2.pop(0))
if L1:
temp.extend(L1)
if L2:
temp.extend(L2)
return temp
def msort(array):
if len(array) == 1:
return array
if not array:
raise ValueError('the list is empty')
middle = len(array)/2
return merge(msort(array[:middle]),msort(array[middle:]))
print msort(array)
时间复杂度：最差和最优都是O(nlogn)，递归深度是logn,每次遍历需要经过O(n)次计算。
空间复杂度：n+O(logn)=O(n),因为每次递归会创建一个临时数组。
再用JAVA再实现一遍：
public static int[] mergeSort(int[] array){
if (array == null) return null;
int len = array.length;
if (len == 1) return array;
int left = 0,right = len - 1;
doMergeSort(array,left,right);
return array;
}
public static void doMergeSort(int[] array,int left,int right){
if (left >= right) return;
int mid = left + right >> 1;
doMergeSort(array,left,mid);
doMergeSort(array,mid+1,right);
doMerge(array,left,mid,right);
}
public static void doMerge(int[] array,int left,int mid,int right){
System.out.println("zong"+(right-left+1));
int[] result = new int[right-left+1];
int i = left,j = mid + 1;
int index = 0;
while (i<=mid && j <= right){
if (array[i] > array[j]){
result[index] = array[j++];
}else {
result[index] = array[i++];
}
index++;
}
while (i<=mid){
result[index++] = array[i++];
}
while (j<=right){
result[index++] = array[j++];
}
int rindex = 0;
for (int pos = left;pos<=right;pos++){
array[pos] = result[rindex++];
}
}
5、插入排序
思路：像相对有序的序列中插入元素，从后往前遍历有序序列，如过当前位置比要插入的元素小，该元素就插到其后面，否则一直遍历，知道找到该元素。
def insert_sort(array):
if len(array) == 1:
return array
for index in range(1,len(array)):
j = index
insert_ele = array[index]
while j>0 and array[j-1] > insert_ele:
array[j] = array[j-1]
j -= 1
array[j] = insert_ele
insert_sort(array)JAVA版本：
public static int[] insertSort(int[] array){
int len = array.length;
if (len == 1) return array;
for (int i=1;i<len;i++){
int j = i;
int insertData = array[j];
while (j>0 && insertData < array[j-1]){
array[j] = array[j-1];
j--;
}
array[j] = insertData;
}
return array;
}
时间复杂度：
最优，即数组已经排好序，那么复杂度即未O(n)。
平均和最差O(n^2)
稳定性：稳定
空间复杂度：O(1)
6.堆排序
堆排序在寻找N个最大值和N个最小值的时候效率更高。
原理：构成堆，将末端值与根节点交换
稳定度：不稳定
时间复杂度：O（nlogn）
def make_heap(array,start,end):
lchild = lambda x:2*x+1
rchild = lambda x:2*x+2
root = start
while True:
left = lchild(root)
if left > end:
break
right = rchild(root)
child = right if right <= end and array[left]<array[right] else left
if array[child] <= array[root]:
break
else:
array[root],array[child] = array[child],array[root]
root = child
def list_heap(array):
for i in xrange(len(array)/2,-1,-1):
make_heap(array,i,len(array)-1)
def hsort(array):
list_heap(array)
for end in xrange(len(array)-1,0,-1):
array[0],array[end] = array[end],array[0]
make_heap(array,0,end-1)
return array
if __name__=="__main__":
array=[3,7,1,8,230,56,100,34,12,40,9,54,67,24,26]
print hsort(array)JAVA版本：
public static int[] heapSort(int[] array){
if (array == null) return null;
int len = array.length;
if (len == 1) return array;
heapify(array);
for (int end = len -1;end >0;end--){
int temp = array[0];
array[0] = array[end];
array[end] = temp;
siftUp(array,0,end-1);
}
return array;
}
private static void heapify(int[] array){
int len = array.length;
for (int i = len / 2 ;i>=0;i--){
siftUp(array,i,len -1);
}
}
private static void siftUp(int[] array,int root,int end){
while (true){
int lchild = 2 * root + 1;
int rchild = 2 * root + 2;
if (lchild > end || rchild < root) break;
int maxChild = rchild <= end && array[lchild] <= array[rchild] ? rchild : lchild;
if (array[maxChild] > array[root]){
int temp = array[maxChild];
array[maxChild] = array[root];
array[root] = temp;
root = maxChild;
}else break;
}
}
--------EOF---------
微信分享/微信扫码阅读
微信分享/微信扫码阅读
