常用排序算法总结(未完成）

Summary

时间复杂度

• 平均情况下：快排，希尔排序，归并排序，堆排都是nlogn，其余都是n^2；特殊情况是基数排序，复杂度是d(n+rd)（其中，n是关键字数，d是关键字的关键字位数，如930，d=3；rd是关键字基的个数，基指的是构成关键字的符号，如关键字为数值时，构成关键字的符号就是0-9，因此rd=10）
• 最坏情况下：快排为n^2，都与平均情况相同
• 助记：快些以nlogn速度归队 (这四种排序的平均复杂度都是nlogn)

空间复杂度

• 快排：nlogn
• 归并排序：n
• 基数排序：rd
• 其余：1

初始情况

直接插容易插变成n，起泡起的好变成n，容易插和起的好指的是初始序列有序

稳定性

情绪不稳定，快些选一堆好友来聊天

快排，希尔排序，简单选择排序，堆排序是不稳定的，其他都是稳定的

排序原理

• 经过一趟排序，能够保证一个关键字到达最终位置，这样的排序是交换类的那两种(起泡，快排)和选择类的那两种(简单选择，堆排)
• 排序算法的关键字比较次数和原始序列无关----简单选择排序和折半插入排序
• 排序算法的排序躺数和原始序列有关----交换类的排序
• 借助于**“比较”进行排序的算法，最坏情况下的时间复杂度至少是nlogn**

直接插入排序和折半插入排序

二者最大的区别在于查找插入位置的方式不同。直接插入按照顺序查找的方式，而折半插入按折半查找的方式

Bubble Sort

//java语言实现
public class BubbleSort {
    public void sort(int[] a)
    {
        for(int i = 0 ; i< a.length ; ++i)
        {
            for(int j = i; j< a.length; ++j)
            {
                if(a[i] > a[j])
                {
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }
            }
        }
    }
}

#python语言实现
class Solution:
    def bubble_sort(self, my_list):
        for passnum in range(len(my_list)-1, 0, -1):
            for i in range(passnum):
                if my_list[i] > my_list[i + 1]:
                    temp = my_list[i]
                    my_list[i] = my_list[i + 1]
                    my_list[i + 1] = temp

Selection Sort

Insertion Sort

Shell Sort

Merge Sort

Quick Sort

//java语言实现
public class QickSort {
    public void sort(int[] a, int left, int right)
    {
        if(left >= right) return;
        int pivotValue = partition(a, left ,right);
        sort(a,left,pivotValue - 1);
        sort(a,pivotValue + 1 ,right);
    }
    public int partition(int[] a, int left, int right)
    {
            int pivotValue = a[left];
            int i = left;
            int j = right + 1;
            while (true)
            {
                while (a[++i] < pivotValue) if(i == right) break;
                while (pivotValue < a[--j]) if (j == left) break;
                if(i >= j) break;
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
            int temp = a[left];
            a[left] = a[j];
            a[j] = temp;
            return j;
    }
}

#python语言实现

class Solution:

    def quick_core(self, my_list, first, end):
        if first < end:
            split_point = self.partition(my_list, first, end)

            self.quick_core(my_list, first, split_point - 1)
            self.quick_core(my_list, split_point + 1, end)

    def partition(self, my_list, first, end):

        pivot_value = my_list[first]

        first_mark = first + 1
        end_mark = end

        flag = True

        while flag:
            while first_mark <= end_mark and my_list[first_mark] <= pivot_value:
                first_mark = first_mark + 1

            while my_list[end_mark] >= pivot_value and end_mark >= first_mark:
                end_mark = end_mark - 1

            if end_mark < first_mark:
                flag = False
            else:
                temp = my_list[first_mark]
                my_list[first_mark] = my_list[end_mark]
                my_list[end_mark] = temp

        temp = my_list[first]
        my_list[first] = my_list[end_mark]
        my_list[end_mark] = temp

        return end_mark