使用matlab实现排序问题

请学习遍历排序，冒泡排序，快速排序算法，画出3种算法的流程图（从小到大排序），并分析3种排序方法的时间复杂度。

遍历排序
- 原理:对待排序数组进行遍历，第一次取第一个数，然后把它和之后的所有数进行比较，范围为1 ~ n，找出最大的数，并将它放在最后一位，然后再从第一位开始，比较范围为1 ~ n-1，找出第二大的数，放置在倒数第二位，以此类推。
- 流程图
- 复杂度：共有两层循环，第一层循环划定比较的范围，第二层进行比较。其外层循环执行 n - 1次。内层循环最多的时候执行n次，最少的时候执行1次，平均执行 (n+1)/2次。所以循环体内的比较约执行 n(n-1)/2次，复杂度为$O(n^2)$。
冒泡排序
- 原理：对数组进行遍历，第一次遍历从数列第一项开始，比较相邻的两项，并且交换顺序排错的项，使每个局部的最大值放在正确的位置。第二次遍历从第二项开始，操作与第一遍一致，直至数组末尾。
- 流程图
- 复杂度
  
  共有两层循环，第一层循环划定比较的范围，第二层进行比较和操作。其外层循环执行 $n - 1$次。内层循环最多的时候执行n次，最少的时候执行1次，平均执行 (n+1)/2次。所以循环体内的比较交换约执行 n(n-1)/2次，复杂度为$O(n^2)$。
  
  按最为复杂的情况为例计算，每次比较都会有三次操作，第一轮共有n次比较，第二次共有n-1次，以此类推：

$$
sum = 3\times[n+(n-1)+(n-2)+…+2+1)]=3\times \frac{n\times (n-1)}{2}=\frac{3}{2}(n^2-n)\
\therefore 复杂度为O(n^2)
$$

快速排序
- 原理:先去确定一个基准数，通过一趟排序将要排序的数据分割成独立的两部分，其中基准数左边的一部分的所有数据比基准数小，基准数右边的所有数据要大于基准数，再按这种方法对这两部分数据分别进行快速排序，直至每部分都只有一个数时结束。整个排序过程可以递归进行，使整个数据变成有序序列。
- 流程图
  
  快速排序算法通过多次比较和交换来实现排序，其排序流程如下：
  - 首先设定一个分界值，通过该分界值将数组分成左右两部分。
  - 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
  - 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
  - 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
    
    一次排序的流程图：
- 复杂度
  
  设n为待排序数组中的元素个数，$T(n)$为算法需要的时间复杂度，则
  $$
  T(n)=\begin{cases}
  D(1)& \text{n$\le$1}\
  D(n)+T(I_1)+T(I_2)& \text{n>1}
  \end{cases}
  $$
  其中$D(n)=n-1$，为一次快排需要的比较次数，一次快排结束后将数组分为两部分$I_1,I_2$。

最好情况下，每一次划分正好将数组分为长度相等的两半

$$
T(n)=\begin{cases}
D(1)& \text{n$\le$1} \
D(n)+T(n/2)+T(n/2)& \text{n>1}
\end{cases}
\
T(n)=D(n)+2T(n/2)=…=D(n)+2D(n/2)+…+2^kD(n/2^k)\
=n-1+2(n/2-1)+…+2^k(n/2^k-1)\
=n-1+n-2+…+n-2^k\
\because k = log_x n\
\therefore 原式 = (k+1)n-(1+2+…+2^k)\
=(k+1)-\frac{2^0(1-2^{k+1})}{1-2}\
=(k+1)n-2·2^k+1\
=nlog_2n-n+1\sim O(nlog_2n)
$$
最坏的情况：每次划分都将数组分为了1和n-1两部分

$$
T(n)=\begin{cases}
D(1)& \text{n$\le$1}\
D(n)+T(1)+T(n-1)& \text{n>1}
\end{cases}
\
T(n)=D(n)+T(n-1)=D(n)+D(n-1)+T(n-2)\
=D(n)+D(n-1)+D(n-2)+…+D(1)\
=n-1+n-2+…+1+0\
=\frac{n(n-1)}{2}\sim O(n^2)
$$
平均时间复杂度：任意一种划分情况出现的概率都相等

$$
T(n)=D(n)+\frac{1}{n}\sum_{i=0}^{n-1}[T(i)+T(n-i)]=D(n)+\frac{2}{n}\sum_{i=0}^{n-1}T(i)\
T(n-1)=D(n-1)+\frac{2}{n-1}\sum_{i=0}^{n-2}T(i)\
\therefore nT(n)-(n-1)T(n-1)=2(n-1)+2T(n-1)\
\frac{T(n)}{n+1}=\frac{T(n-1)}{n}+\frac{2(n-1)}{n(n+1)}\
\therefore B(n)=\frac{T(n)}{n+1},得B(n)-B(n-1)=\frac{2(n-1)}{n(n+1)}\
可展开该递推式：B(n)=B(n-1)+\frac{2(n-1)}{n(n+1)}\
=B(n-2)+\frac{2(n-2)}{n(n-1)}+\frac{2(n-1)}{n(n+1)}=B(1)+\sum_{i=1}^n\frac{2(i-1)}{i(i+1)}\
=0+\sum_{i=1}^n[\frac{2}{i}-\frac{4}{i(i+1)}]=\sum_{i=1}^n\frac{2}{i}-4\sum_{i=1}^n[\frac{1}{i}-\frac{1}{i+1}]=\sum_{i=1}^n\frac{2}{i}-\frac{4n}{n+1}\
\approx 2(ln(n)+0.577)-\frac{4n}{n+1}\
\therefore T(n)=(n+1)B(n)=2(n+1)(ln(n)+0.577)-4n=2nlnn-2.846n+1.154\sim O(nlog_2n)
$$

所以，快速排序最好时间复杂度为 $O(nlog_2n)$ ,最坏时间复杂度为$O(n^2)$ ,平均时间复杂度为 $O(nlog_2n)$

请自行编写程序完成三种排序，但数据集均为[0，1]之间的浮点数时，比较上述三种算法及matlab内置排序sort函数的快慢。

遍历排序

function output = traverse(input)
%TRAVERSE 遍历排序函数
    n=length(input);
    x = input;
    for i=1:n
        amin = x(1);
        mini = 1;
        for j=1:n-i      
            if amin >= x(j+1)
                amin = x(j+1);
                mini = j+1;
                j = j + 1;
            end
        end
        x(n+1)=amin;
        x(mini)=[];
    end
    output = x;
end

冒泡排序

function output = bubble(input)
%BUBBLE 冒泡排序函数
    n=length(input);
    x = input;
    for i=1:n
        for j=1:n-i
            if x(j)>x(j+1)
                t = x(j);
                x(j) = x(j+1);
                x(j+1) = t;
            end
        end
    end
    output = x;
end

快速排序

function output=quick_sort(intput,low,high)
%QUICK 快排函数
    n=length(intput);
    x = intput;
    if low<high
        [x,key]=getkey(x,low,high);
        x=quick_sort(x,low,key-1);
        x=quick_sort(x,key+1,high);
    end
    output = x;
end

function [x,index]=getkey(x,i,j)
    key=x(i);
    while i<j
        while i<j && x(j)>=key
            j=j-1;
        end

        if i<j
            x(i)=x(j);
        end

        while i<j && x(i)<=key
            i=i+1;
        end

        if i<j
            x(j)=x(i);  
        end

    end
    x(i)=key;
    index=i;
end

比较快慢（对于大小在[0,1]之间的浮点数，取长度为10，100，1000来计算）

clear;clc;
for i =1:10
    x = rand(1,10);
    tic;x1 = traverse(x);
    t1(i) = toc;
    tic;x2 = bubble(x);
    t2(i) = toc;
    tic;x3 = quick_sort(x,1,length(x));
    t3(i) = toc;
    tic;x4 = sort(x);
    t4(i) = toc;
end
fprintf("数组长度为10时\n遍历排序耗时%fs\n冒泡排序耗时%fs\n快速排序耗时%fs\nsort排序耗时%fs\n",mean(t1),mean(t2),mean(t3),mean(t4))
for i =1:10
    x = rand(1,100);
    tic;x1 = traverse(x);
    t1(i) = toc;
    tic;x2 = bubble(x);
    t2(i) = toc;
    tic;x3 = quick_sort(x,1,length(x));
    t3(i) = toc;
    tic;x4 = sort(x);
    t4(i) = toc;
end
fprintf("数组长度为100时\n遍历排序耗时%fs\n冒泡排序耗时%fs\n快速排序耗时%fs\nsort排序耗时%fs\n",mean(t1),mean(t2),mean(t3),mean(t4))
for i =1:10
    x = rand(1,1000);
    tic;x1 = traverse(x);
    t1(i) = toc;
    tic;x2 = bubble(x);
    t2(i) = toc;
    tic;x3 = quick_sort(x,1,length(x));
    t3(i) = toc;
    tic;x4 = sort(x);
    t4(i) = toc;
end
fprintf("数组长度为1000时\n遍历排序耗时%fs\n冒泡排序耗时%fs\n快速排序耗时%fs\nsort排序耗时%fs\n",mean(t1),mean(t2),mean(t3),mean(t4))
for i =1:10
    x = rand(1,10000);
    tic;x1 = traverse(x);
    t1(i) = toc;
    tic;x2 = bubble(x);
    t2(i) = toc;
    tic;x3 = quick_sort(x,1,length(x));
    t3(i) = toc;
    tic;x4 = sort(x);
    t4(i) = toc;
end
fprintf("数组长度为10000时\n遍历排序耗时%fs\n冒泡排序耗时%fs\n快速排序耗时%fs\nsort排序耗时%fs\n",mean(t1),mean(t2),mean(t3),mean(t4))

数组长度为10时
遍历排序耗时0.000017s
冒泡排序耗时0.000002s
快速排序耗时0.000004s
sort排序耗时0.000002s
数组长度为100时
遍历排序耗时0.000148s
冒泡排序耗时0.000034s
快速排序耗时0.000028s
sort排序耗时0.000004s
数组长度为1000时
遍历排序耗时0.003035s
冒泡排序耗时0.002749s
快速排序耗时0.000312s
sort排序耗时0.000035s
数组长度为10000时
遍历排序耗时0.283688s
冒泡排序耗时0.280093s
快速排序耗时0.032537s
sort排序耗时0.000263s

说明：可以根据结果看出，对于大小在[0,1]之间的浮点数，四种排序方法速度从快到慢为：sort>快排>冒泡>遍历

针对上面的数据集，验证3种算法的时间复杂度，若数据集均为[0,10]之间的整数，结果又如何？为什么会这样。

若数据集均为[0,10]之间的整数

clear;clc;
for i =1:10
    x = round(rand(1,10)*10);
    tic;x1 = traverse(x);
    t1(i) = toc;
    tic;x2 = bubble(x);
    t2(i) = toc;
    tic;x3 = quick_sort(x,1,length(x));
    t3(i) = toc;
    tic;x4 = sort(x);
    t4(i) = toc;
end
fprintf("数组长度为10时\n遍历排序耗时%fs\n冒泡排序耗时%fs\n快速排序耗时%fs\nsort排序耗时%fs\n",mean(t1),mean(t2),mean(t3),mean(t4))
for i =1:10
    x = round(rand(1,100)*10);
    tic;x1 = traverse(x);
    t1(i) = toc;
    tic;x2 = bubble(x);
    t2(i) = toc;
    tic;x3 = quick_sort(x,1,length(x));
    t3(i) = toc;
    tic;x4 = sort(x);
    t4(i) = toc;
end
fprintf("数组长度为100时\n遍历排序耗时%fs\n冒泡排序耗时%fs\n快速排序耗时%fs\nsort排序耗时%fs\n",mean(t1),mean(t2),mean(t3),mean(t4))
for i =1:10
    x = round(rand(1,1000)*10);
    tic;x1 = traverse(x);
    t1(i) = toc;
    tic;x2 = bubble(x);
    t2(i) = toc;
    tic;x3 = quick_sort(x,1,length(x));
    t3(i) = toc;
    tic;x4 = sort(x);
    t4(i) = toc;
end
fprintf("数组长度为1000时\n遍历排序耗时%fs\n冒泡排序耗时%fs\n快速排序耗时%fs\nsort排序耗时%fs\n",mean(t1),mean(t2),mean(t3),mean(t4))
for i =1:10
    x = round(rand(1,10000)*10);
    tic;x1 = traverse(x);
    t1(i) = toc;
    tic;x2 = bubble(x);
    t2(i) = toc;
    tic;x3 = quick_sort(x,1,length(x));
    t3(i) = toc;
    tic;x4 = sort(x);
    t4(i) = toc;
end
fprintf("数组长度为10000时\n遍历排序耗时%fs\n冒泡排序耗时%fs\n快速排序耗时%fs\nsort排序耗时%fs\n",mean(t1),mean(t2),mean(t3),mean(t4))

数组长度为10时
遍历排序耗时0.000016s
冒泡排序耗时0.000004s
快速排序耗时0.000004s
sort排序耗时0.000002s
数组长度为100时
遍历排序耗时0.000154s
冒泡排序耗时0.000035s
快速排序耗时0.000033s
sort排序耗时0.000004s
数组长度为1000时
遍历排序耗时0.003092s
冒泡排序耗时0.002701s
快速排序耗时0.000464s
sort排序耗时0.000023s
数组长度为10000时
遍历排序耗时0.300904s
冒泡排序耗时0.274208s
快速排序耗时0.135769s
sort排序耗时0.000229s

说明：可以根据结果看出，对于大小在[0,10]之间的整数，四种排序方法速度从大到小为：sort>快速>冒泡>遍历

结果与对浮点数排序一致，各种比较操作、赋值操作本质上对整数或是浮点数的运算速度接近，所以结果并不会出现太大的区别

调研并实现一种算法，使得对数据集均为[0,10]之间的整数，算法复杂度低于快速排序。

答：可用希尔排序。

希尔排序介绍
- 希尔排序是将待排序的数组元素按下标的一定增量分组，分成多个子序列，然后对各个子序列进行直接插入排序算法排序；然后依次缩减增量再进行排序，直到增量为1时，进行最后一次直接插入排序，排序结束。
计数排序复杂度为$O(n^{1.3})$，当排序的数是0~10范围内的数且n>2.5时，计数排序复杂度低于快排复杂度$O(nlog_2(n))$。

function output = xier(input)
%XIER 希尔排序函数
    x = input;
    n = length(x);
    gap=floor(n/2); %设置初始增量，一般取为数组长度的一半
    while gap>0
        i=gap;
        while i<n
            j=i;
            current = x(i+1);
            while j-gap>=0 && current<x(j-gap+1) % 若后面的值大于前面的值，则交换
                x(j+1)=x(j-gap+1);
                j=j-gap;
            end
            x(j+1)=current;
            i=i+1;
        end
        gap=floor(gap/2); % 每次按增量遍历结束后，将增量缩小为原来的1/2，直至gap=0
    end
    output = x;
end

比较

clear;clc;
for i =1:10 
    x = round(rand(1,10)*10);
    tic;x1 = quick_sort(x,1,length(x));
    t1(i) = toc;
    tic;x2 = xier(x);
    t2(i) = toc;
end
fprintf("数组长度为10时，快速排序耗时%fs\n希尔排序耗时%fs\n",mean(t1),mean(t2))

for i =1:10 
    x = round(rand(1,100)*10);
    tic;x1 = quick_sort(x,1,length(x));
    t1(i) = toc;
    tic;x2 = xier(x);
    t2(i) = toc;
end
fprintf("数组长度为100时，快速排序耗时%fs\n希尔排序耗时%fs\n",mean(t1),mean(t2))

for i =1:10 
    x = round(rand(1,100)*10);
    tic;x1 = quick_sort(x,1,length(x));
    t1(i) = toc;
    tic;x2 = xier(x);
    t2(i) = toc;
end
fprintf("数组长度为100时，快速排序耗时%fs\n希尔排序耗时%fs\n",mean(t1),mean(t2))

数组长度为10时，快速排序耗时0.000163s
希尔排序耗时0.000059s
数组长度为100时，快速排序耗时0.000092s
希尔排序耗时0.000049s
数组长度为100时，快速排序耗时0.000075s
希尔排序耗时0.000040s

可看出，希尔排序耗时均小于快速排序。

利用自己实现的算法，编写一个GUI演示窗口。要求：能够输入一列向量（长度不超过15），选择一种排序算法，动态绘制排序过程。

编写绘图函数，并在之前编写的排序函数中当数据变化后调用绘图函数

function draw(x)
    time=0.3; 
    clf; % 清除之前的图形
    bar(x); % 绘制柱状图
    pause(time); % 延时函数，使得结果更易观察
end

编写APP（使用App designer）

共包括四个组件：
- EditField:用于输入待排序的数组，数组各元素之间用空格隔开即可
- ListBox:输入待排序数组后，选择排序方法，共用四种供选择
- StartButton:完成以上两步之后，点击该按钮即可开始排序
- EditField_2:排序完成后显示排序好的（从小到大）的数组
点击打开文件“sort_tool_exported.m”,点击运行即可显示GUI。

点击“Start”后，弹出figure图窗，动态显示排序过程

排序结束后，会在EditField2窗口中显示排序好的数组。