快速排序算法的平均性能非常好：期望时间复杂度为O(nlgn)，而且其中的隐含的常数因子非常小，另外它具有原址排序的优点，即在内部排序，不用再新建一个数组。与归并排序一样，快速排序也是用了分治法的思想。快速排序主要思想是：将一个大数组分成两块，并且两块的中间的一个数起分割作用，数的左边均小于它，数的右边均大于它。然后将子数组再分割为两块，同样的规律......直到子数组的元素只有一个位置，于是所有的地方都已经排好序了。所以，我们可以想象，分割的终止条件是数组只有一个元素了。
 
 

分割
 
首先，我们实现对一个数字进行分割，并且找出这个分割数（主元，pivot）的位置。思想很简单，先假设第一个元素为分割数（主元），然后，我们设定两个移动的索引分别是left和right，left从左往右遍历，遇到比主元小的直接跳过，遇到不满足的就停下;同理，right从右往左遍历，遇到比主元大的就跳过，遇到不满足的就停下。于是，当两者都停下时，我们比较一下left与right的位置，若left在right的左边，则我们将left和right分别所指的两个元素进行互换，交换过后，再分别接着遍历，同样的规律，直到right在left的左边为止。此时，我们将pivot和right分别所指的两个数进行交换，并且返回right。那么，right的值就是分割数的索引，即主元的位置。具体代码如下：
 

int partition(int* A,int start,int end)
{
int left=start+1;
int right=end;
int tmp;
while(right>left) {
while(*(A+left)<*(A+start)) {
left++;
}
while(*(A+right)>*(A+start)) {
right--;
}
if(left<right) {
tmp=*(A+left);
*(A+left)=*(A+right);
*(A+right)=tmp;
}
}
tmp=*(A+right);
*(A+right)=*(A+start);
*(A+start)=tmp;
return right;
}
 
 
 
分治法的运用
 
现在假设我们已经将一个数组分为了两个部分了，中间由一个主元分割开。那么，我们接下来要做的就是继续分别对这两个子数组进行分割，寻找主元。在这个过程中，要明白主元的位置一定是固定的。因此，显然，我们的做法就是一直分割下去直到子数组只有一个元素为止，即一开始就有right=left。那么，在这个整体过程中，我们将一个大数组二分直到只有一个元素位置的步骤是logn步，然后我们找主元相当于每次确定一个元素的位置，因此共有n个元素，因此，算法复杂度为nlogn。
void quickSort(int* A,int start,int end)
{
if(start<end) {
int pivot=partition(A,start,end);
quickSort(A,start,pivot-1);
quickSort(A,pivot+1,end);
}
}
 
 

主函数
 
#include<stdio.h>
int main()
{
int a[7]={3,2,5,0,9,8,1};
quickSort(a,0,6);
int i;
for(i=0;i<7;i++)
printf("%d\n",a);
return 0;
}
 
 
 

编写Makefile
 
# this is a makefile
main.o:main.c quickSort.o partition.o
gcc quickSort.o partition.o main.c -o main.o
quickSort.o:quickSort.c partition.o
gcc -c quickSort.c
partition.o:partition.c
gcc -c partition.c
 
 
 
 
来源： 张下泽旺 深度学习每摘要
智造家 查看全部

前言：本期穿插讲解一些《算法与数据结构系列》（Algorithms and Data Structures，题中简称AD），此篇为第二期——组合与排列算法。



    组合与排列的知识我们在高中就已经学习过了，它们的最大区别就是，如果我们在实际问题中需要考虑元素之间的顺序，就使用排列；如果不用考虑元素之间的顺序，就使用组合。



组合

    所谓组合其实就是对一组物体进行无序地重新排列，例如现在有一数组[1,2,3,4]，要对其元素进行两两组合，可以得到以下六种组合：

    1，2

    1，3

    1，4

    2，3

    2，4

    3，4

    若一共有N个元素，需要从中取出M个元素进行组合，则一共有C（N，M）=N*（N-1）*...*（N-M+1）/（1*2*...*M）=N！/[M！（N-M）！]种组合方式。


    实际问题如：在一个礼品店里有种礼品，而只需要购买其中2种，一共有10*9/2=45种购买方式。


    在使用计算机处理组合算法时，可以采用递归算法，即每次从原数组中取出两个元素存放到新数组中。


    

#include<stdio.h>

#define N 4

#define M 2




//全局变量，a为给定数组，b为存储组合的数组

int a[N];

int b[M];




//函数声明

void comb(int,int);

void print();




//打印数组b

void print()

{

    int i;

    for(i=0;i<M;i++) {

        printf("%d ",b);

    }

    printf("\n");

}




//组合，递归方式

void comb(int n,int m)

{

    int i;

    if(m==0) {

        print();

        return;

    } else {

        for(i=n-1;i>=0;--i) {

            b[m-1]=a;

            comb(i,m-1);

        }

    }

}




int main()

{

    int i;

    for(i=0;i<N;i++)

        a=i+1;//初始化数组

    comb(N,M);

    return 0;

}

    




全排列


假设现在给定数组1,2,3，其全排列如下所示：

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

若一共有N个元素进行全排列，则一共有P（N，N）=N！种组合方式。

在编写计算机代码时，同样采取递归的算法。

#include <stdio.h>

#define N 3



int a[N];  //全局变量，数组



//函数声明

void perm(int); /*求数组的全排列 */

void print();

void swap(int, int);




//主函数

int main(){

    int i;

    for(i = 0; i < N; ++i){

        a = i + 1;

    }

    perm(0);

    return 0;

}



//全排列函数

void perm(int offset){

    int i, temp;

    if(offset == N-1){  // BaseCase

        print();

        return;

    }else{

        for(i = offset;i < N; ++i){

            swap(i, offset);//交换前缀

            perm(offset + 1);//递归

            swap(i, offset);//将前缀换回来，继续做前一次排列

        }

    }

}




//打印数组

void print(){

    int i;

    for(i = 0; i < N; ++i)

        printf(" %d ",a);

    printf("\n");

}   




//交换全局数组的两个指定元素

void swap(int i, int offset){

    int temp;

    temp = a[offset];

    a[offset] = a;

    a = temp;

}



来源： 张泽旺 深度学习每日摘要
智造家 查看全部