各种排序算法

插入排序:

#include <stdio.h>
#define A 1

void printInfo(int a[],int l);
void InsertionSort(int a[],int l);
int main(){
    int a[]={0xffff,49,38,65,97,76,13,27,49};//a[0]置空,不参与排序
    int l=8;
    printInfo(a,l);
    InsertionSort(a,l);
    return 0;
}
void InsertionSort(int a[],int l){//从小到大排序
    int i=1;
    int j;
    int temp;
    for(i=2;i<=l;i++){//a[i]是需要处理的那个,前面的i-1个是有序的数据
        if(a[i]<a[i-1]){//a[i-1]应该是前面的排好序里面的最大的那个,如果a[i]<a[i-1]说明a[i]需要插入前面进行排序
            temp=a[i];//把当前需要插入的数字记录下来
            printf("temp=%d\n",temp);
#if A
            for(j=i-1;a[j]>=temp&&j>=1;j--){//
                a[j+1]=a[j];//把a[j]后移一位
            }
            a[j+1]=temp;
#else
            for(j=i;a[j]>=temp&&j>=1;j--){//先把a[j]前面的数字向后移到a[j]的位子上,需要找到一个小于temp的数字,这时候循环会停止
                a[j]=a[j-1];
            }
            a[j+1]=temp;//成功进入一轮插入 //a[j]是小于tmep的第一个数字,把数字放在[j]后
#endif
        }
        printf("i=%d\t",i);
        printInfo(a,l);
    }
}
void printInfo(int a[],int l){
    int i=1;
    for(i=1;i<=l;i++){
        printf("%d\t",a[i]);
    }
    printf("\n");
}

快速排序:

#include <stdio.h>
#include "print.h"
#include "data.h"
#define SWAP(a,b)   {int temp=a;a=b;b=temp;}
void QuickSort(int a[],int l);
void Qsort(int a[],int i,int j);

int main(void){
    printInfo(a,l);
    QuickSort(a,l);
    printInfo(a,l);
    return 0;
}

void QuickSort(int a[],int l){
    int i=1;
    int j=l;
    j=l;
    i=1;
    Qsort(a,i,j);
}
void Qsort(int a[],int i,int j){
    if(i>=j){
        return;
    }
    int key=a[i];
    int left=i;
    int right=j;
    while(i!=j){                //升序排列,左边的是比较小的,右边的是比较大的,如果在右边找打比key小的,就停了
        while(a[j]>=key&&j>i){  //请注意这里,为什么是先从右边的j开始向后移呢,
            j--;                //如果每次是从i(left)端扫描移动的话,就会出现
        }                       //最后一次i和j相遇 i向右走,走到j那边,然后
        while(a[i]<=key&&i<j){  //把j上面比key大的数字和开始的key交换,这就出现了,序列最左边的一个数字,比key大,不符合升序
            i++;
        }
        if(left<j) {
            SWAP(a[left],a[j])
        }
    }
    Qsort(a,left,i-1);
    Qsort(a,i+1,right);
}
/*  6 1 2 7 9 3 4 5 10 8
 *  从右边开始扫描:
 *      (j)=5 (i)=7 交换
 *            i       j
 *      6 1 2 5 9 3 4 7 10 8
 * ---------------------------------
 *      (j)=4 (i)=9 交换
 *              i   j
 *      6 1 2 5 4 3 9 7 10 8
 * ---------------------------------
 *      (j)=3 (i)=3遇到j
 *      把6放进位置
 *               ij
 *      3 1 2 5 4 6 9 7 10 8
 * ---------------------------------
 *  从左边开始扫描:
 *      (i)=7   (j)=5 交换
 *            i       j
 *      6 1 2 5 9 3 4 7 10 8
 * ---------------------------------
 *      (i)=9   (j)=4 交换
 *              i   j
 *      6 1 2 5 4 3 9 7 10 8
 * ---------------------------------
 *      (i)=9 (j)=9 遇到j
 *                  ij
 *      6 1 2 5 4 3 9 7 10 8
 *      9 1 2 5 4 3 6 7 10 8
 * 
*/

 

 

更新中

发表评论

邮箱地址不会被公开。