笔记

数据结构与算法

排序

常见排序复杂度

传统排序算法

Selection Sort

• The worst case complexity is O(n^2^)
• The best case complexity is O(n^2^)

1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3. 重复第二步，直到所有元素均排序完毕。

public class Selection_Sort {
    public static int[] sort(int[] array, int n){
        for(int StartingIndex = 0; StartingIndex < n; StartingIndex++){
            int CurrentSmallestIndex = StartingIndex;
            for(int tmp = StartingIndex; tmp < n; tmp++){
                if(array[tmp] < array[CurrentSmallestIndex]){
                    CurrentSmallestIndex = tmp;
                }
            }
            //Swap
            int tmp = array[StartingIndex];
            array[StartingIndex] = array[CurrentSmallestIndex];
            array[CurrentSmallestIndex] = tmp;
        }
        return array;
    }
}

Rank Sort

• The idea is that for every element in the array we count the number of elements smaller than it
  • ​ The complexity of rank sort O(n^2^)
• When compared with selection sort, can we tell which is better
  • ​ No, they are the same

1. 以第一个数为基准，寻找比他小的数字数量作为Rank
2. 在新数组中Rank的位置放入这个数字
3. 循环以第N个数为基准

public class Rank_Sort {
    public static int[] sort(int[] array, int n) {
        int[] res = new int[n];
        for (int CurrentIndex = 0; CurrentIndex < n; CurrentIndex++) {
            int rank = 0;
            for (int tmp = 0; tmp < n; tmp++) {
                if (array[tmp] < array[CurrentIndex])
                    rank++;
            }
            res[rank] = array[CurrentIndex];
        }
        return res;
    }
}

插入排序Insertion_Sort（将元素插入有序数组中）

• What is the worst case complexity of insertion sort? 􏰀
  • ​ O(n2)
• When does this happen?
  • ​ When the data is sorted in reverse order
• What is the best case complexity of insertion sort? 􏰀
  • ​ O(n)
• When does this happen?
  • ​ When the data is already sorted

1. 从第一个元素开始，该元素可以认为已经被排序
2. 维护一个完成排序的部分，从已排序的位置往前移动
3. 如果两个当前元素比前一个小，那么交换他们
4. 已排序位置+1

public class Insertion_Sort {
    public static int[] sort(int[] array, int n){
        int CurrentSortedIndex = 0;
        while(CurrentSortedIndex < n){
            int Comparer = CurrentSortedIndex;
            while(Comparer > 0 && array[Comparer] < array[Comparer -1]){
                //Swap
                int tmp = array[Comparer];
                array[Comparer] = array[Comparer - 1];
                array[Comparer - 1] = tmp;
                Comparer--;
            }
            CurrentSortedIndex++;
        }
        return array;
    }
}

高级排序算法

快速排序

The idea behind quicksort and other $O(n ∗ log(n))$ sorting algorithms is based on idea that sorting $\frac{x}{n}$ elements x times is more efficient that sorting n elements.

Lets say we have 100 elements
If we use an O(n^2^) algorithm to sort them the cost will be 10000
If we separate them into two partitions of 50 and sort these the cost will be 5000 = (2 * 50^2^)
Many advances sorting techniques are based on this idea

1. 数列中最左边的元素，称为 “基准”（pivot）;
2. 在左右不相等的情况下，从右往左看，如果当前数字比pivot小则停止
3. 在左右不相等的情况下，从右继续看，如果当前数字比pivot大则停止
4. 交换这两个数
5. 将pivot与左右相等位置交换
6. 递归调用，让high和low分别向两侧移动一位

public class Test_Quick_Sort {
    public static int[] swap(int[] array, int index1, int index2){
        int tmp = array[index1];
        array[index1] = array[index2];
        array[index2] = tmp;
        return array;
    }
    public static void sort(int[] array, int low, int high){
        int right,left, middle;
        int tmp;
        if(low > high){
            return;
        }
        left = low;
        right = high;
        middle = array[low];
        while(left < right){
            //!!!!!!!！！！!!先看右边！！！！！！！！！！！！
            //否则一定会出错
            //排序会造成一部分排好而另一部分没有排好
            while(array[right] >= middle && left < right){
                right--;
            }
            while(array[left] <= middle && left < right){
                left++;
            }

            if(left < right) {
                tmp = array[right];
                array[right] = array[left];
                array[left] = tmp;
            }
        }
        array[low] = array[left];
        array[left] = middle;
        sort(array, low, right-1);
        sort(array, right+1, high);
    }
    public static void main(String[] args) {
        int [] a = {1,6,8,7,3,5,16,4,8,36,13,44};
        sort(a,0,a.length-1);
        for (int i:a) {
            System.out.print(i + " ");
        }
    }
}

归并排序 Merging Sort (递归拆分，再合并)

public class Merging_Sort {
    public static void merge(int[] a, int start, int mid, int end) {
        int[] tmp = new int[a.length];
        System.out.println("merge " + start + "~" + end);
        int i = start, j = mid + 1, k = start;
        while (i <= mid && j <= end) {
            if (a[i] < a[j])
                tmp[k++] = a[i++];
            else
                tmp[k++] = a[j++];
        }
        //如果有一个先到结束，就会丢失数据，下面到代码把缺失的数据补回去
        while (i <= mid)
            tmp[k++] = a[i++];
        while (j <= end)
            tmp[k++] = a[j++];
        for (i = start; i <= end; i++)
            a[i] = tmp[i];
        for (int p : a)
            System.out.print(p + " ");
        System.out.println();
    }

    static void mergeSort(int[] a, int start, int end) {
        if (start < end) {
            int mid = (start + end) / 2;
            mergeSort(a, start, mid);// 左边有序
            mergeSort(a, mid + 1, end);// 右边有序
            merge(a, start, mid, end);
        }
    }

def merge_sort(ary):
    if len(ary) <= 1 : return ary
    num = int(len(ary)/2)       #二分分解
    left = merge_sort(ary[:num])
    right = merge_sort(ary[num:])
    return merge(left,right)    #合并数组

def merge(left,right):
    '''合并操作，
    将两个有序数组left[]和right[]合并成一个大的有序数组'''
    l,r = 0,0           #left与right数组的下标指针
    result = []
    while l<len(left) and r<len(right) :
        if left[l] < right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result += left[l:]
    result += right[r:]
    return result

桶排序

• Each bucket is a linked list

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

• 在额外空间充足的情况下，尽量增大桶的数量
• 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

1. 什么时候最快

   当输入的数据可以均匀的分配到每一个桶中。

2. 什么时候最慢

   当输入的数据被分配到了同一个桶中。

3. 示意图

   元素分布在桶中：

​ 然后，元素在每个桶中排序：

基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。

• 基数排序：根据键值的每位数字来分配桶；
• 桶排序的执行次数：看数字有多少位就执行多少次

冒泡排序（相邻交换）

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对第0个到第n-1个数据做同样的工作。这时，最大的数就“浮”到了数组最后的位置上。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
5. 某一趟遍历如果没有数据交换，则说明已经排好序了，因此不用再进行迭代了。用一个标记记录这个状态即可。

ßdef bubble_sort(arry):
    n = len(arry)
    for i in range(n-1,0,-1):
        flag = 1
        for j in range(0,i):
            if arry[j] > arry[j+1]:
                arry[j],arry[j+1] = arry[j+1],arry[j]
                flag = 0
        if flag:
             break
    return arry
if __name__ == '__main__':
    disorder_arry  = [10,9,8,7,6,5,4,3,2,1]
    order_arry = bubble_sort(disorder_arry)
    print(order_arry)
#某一趟遍历如果没有数据交换，则说明已经排好序了，因此不用再进行迭代了。用一个标记记录这个状态即可。

⬆️这种排序没有讲过

数据结构

栈

性质

• last-in-first-out (LIFO) principle
• Items are pushed onto the stack (insertion)
• 􏰀Items are popped off of the stack (removal)

方法列表

• 􏰀 push(i): The integer i is inserted onto the top of the stack

• 􏰀 pop(): The object on the top of the stack is removed and returned by

  the method

• 􏰀 top(): The object on the top of the stack is returned by the method

  but not removed

package Stack;
public class Stack{
    private int top=-1; //指向栈顶，用于栈的遍历
    private int stackSize=0;//栈的大小
    private char[] stackArray=null;//用于创建栈的数组
    //create stack use array（创建一个指定大小的新栈）
    public void createStack(int size){
        stackSize=size;
        stackArray=new char[size];
    }
    //push element（数据压入）
    public void push(char element){
        if(top!=stackSize-1){  //应在压入数据前判断栈是否为满栈
            stackArray[top+1]=element;
            top++;
        }else{
            System.out.println("Sorry,can`t push!This stack is full!");
        }
    }
    //pop element（数据弹出）
    public void pop(){
        if(!isEmpty()){//在弹出时应判断栈是否为空栈，空栈则无数据可弹出
            // System.out.println("pop->"+stackArray[top]);
            //stackArray[stackSize-1]=0;
            top--;
        }else{
            System.out.println("Sorry,can`t pop!This stack is empty!");
        }
    }
    //look element（查看栈顶数据）
    public char peek(){
        char peekElement=stackArray[top];
        return peekElement;
    }

    //is empty（判断栈是否为空）
    public boolean isEmpty(){
        if(top==-1){
            return true;
        }else{
            return false;
        }
    }
    //is full（判断栈是否为满栈）
    public boolean isFull(){
        if(stackSize!=-1){
            if(top==stackSize-1){
                return true;
            }else{
                return false;
            }
        }else{
            System.out.println("Sorry,this stack is empty!");
            return false;
        }
    }
}