排序算法

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 array

JAVA:

 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---------
本文微信分享/扫码阅读