七大排序算法

第一篇技术文章，今天就把七大排序算法记录下来把。

//冒泡排序
#include "stdafx.h"
#include <stdio.h>
#include<malloc.h>
#include<math.h>
void bubbleSort(int n,int a[]) {

    int flag = 1;                                      //这里的flag主要防止这个序列本身是顺序的，一趟比较完还是0，那么就证明这个数列是顺序的,不需要第二趟了
    for (int i = 0; i < n && flag ==1; i++) {
        flag = 0;
        for (int j = 0; j < n - i-1; j++) {
            if (a[j] > a[j + 1]) {
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;

                flag = 1;
            }
        }
    }
}


//选择排序
void selectSort(int n,int a[]) {

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] > a[j]) {
                int temp = a[j];
                a[j] = a[i];
                a[i] = temp;
            }
        }
    }
}


//直接插入排序
void insertSort(int n,int a[]) {

    int i, j;
    for (i = 1; i < n; i++) {
        int temp = a[i];
        j = i - 1;
        while (temp > a[j] && j >= 0) {
            a[j+1] = a[j--];
        }
        a[j+1] = temp;
    }
}


//快速排序
void swap(int *a, int *b) {

    int temp = *a;
    *a = *b;
    *b = temp;
}

void quickSort(int a[],int s,int t) {
    int i, j;
    if (s < t) {
        i = s;
        j = t+1;

        while (1) {
            do
                i++;
            while (!(a[s] >= a[i] || i == t));
            do
                j--;
            while (!(a[s] <= a[j] || j == s));

            if (i < j) 
                swap(&a[i],&a[j]);
            else
                break;
        }

        swap(&a[s],&a[j]);

        quickSort(a,s,j-1);
        quickSort(a,j+1,t);
    }
}


//希尔排序  其实就是特殊的插入排序，当插入排序的gap=1  就是shell排序  
void shellSort(int a[],int n) {
    
    int gap = n;
    while (gap > 1) {
        gap = gap / 2;

        for (int i = gap; i < n; i++) {
            int temp = a[i];
            int j = i - gap;
            while (temp > a[j] && j >= 0) {
                a[j + gap] = a[j];
                j-=gap;
            }
            a[j + gap] = temp;
        }
    }
}



//堆排序
void swap1(int k[], int i, int j) {
    int temp = k[i];
    k[i] = k[j];
    k[j] = temp;
}

void heapAdjust(int k[], int s, int  n) {
    int i, temp;
    temp = k[s];
    for (i = 2 * s; i <= n; i *= 2) {
        if ( i<n && k[i] < k[i + 1] ) {
            i++;
        }
        if (temp >= k[i]) {
            break;
        }
        k[s] = k[i];
        s = i;
    }
    k[s] = temp;
}

void heapSort(int k[], int n) {
    int i;
    //构建堆，一个大顶堆，或者一个小顶堆
    for (i = n / 2; i > 0; i--) {
        heapAdjust(k, i, n);
    }
    //调整
    for (i = n; i > 1; i--) {
        swap1(k, 1, i);
        //重新构建堆
        heapAdjust(k, 1, i-1);
    }
}


//归并排序（递归实现）
#define MAX_SIZE 11
void mergeing(int *list1, int list1_size, int *list2, int list2_size) {
    
    int i, j, k, m;
    int temp[MAX_SIZE];

    i = j = k = 0;
    while (i < list1_size && j < list2_size) {
        if (list1[i] < list2[j]) {
            temp[k++] = list1[i++];
        }
        else {
            temp[k++] = list2[j++];
        }
    }

    while (i < list1_size) {
        temp[k++] = list1[i++];
    }
    while (j<list2_size){
        temp[k++] = list2[j++];
    }

    for (m = 0; m < list1_size + list2_size; m++ ) {
        list1[m] = temp[m]; 
    }
}

void mergeSort(int k[], int n) {

    if (n > 1) {
        int *list1 = k;
        int list1_size = n / 2;
        int *list2 = k + n / 2;
        int list2_size = n - list1_size;

        mergeSort(list1, list1_size);
        mergeSort(list2, list2_size);

        mergeing(list1, list1_size, list2, list2_size);
    }

}



//归并排序（迭代实现） 
void mergeSort1(int k[], int n) {
    int i, left_min, left_max, right_min, right_max,next;
    int *temp = (int*)malloc(n * sizeof(int));

    for (i = 1; i < n; i *= 2) {    //步长 1，2，4，8，16，第一层1，第二层2，第三层4，。。。
        for (left_min = 0; left_min < n - i; left_min = right_max) {
            right_min = left_max = left_min + i;
            right_max = left_max + i;

            if (right_max > n) {
                right_max = n;
            }

            next = 0;

            while (left_min < left_max && right_min < right_max) {
                if (k[left_min] < k[right_min]) {
                    temp[next++] = k[left_min++];
                }
                else {
                    temp[next++] = k[right_min++];
                } 
            }

            while (left_min < left_max) {
                k[--right_max] = k[--left_max];
            }
            while (next > 0) {
                k[--right_min] = temp[--next];
            }
        }
    }
}

void bitode(int n, int *sum, int *m) {

    char c;
    scanf("%c", &c);
    if (c != '#') {
        *m = *m + 1;
        bitode(n + 1, &(*sum), &(*m));
    }
    if (c == '1')
        *sum = *sum + pow(2, (*m) - n - 1);
}


void main1() {
    
    int sum = 0, m = 0;
    bitode(0, &sum, &m);
    printf("the result is \n %d", sum);
    getchar();

    int a[11] = {333,2,12,43,54,11,65,75,21,34,97};
     
    for (int i = 0; i < 11; i++) {
        printf("%d ", a[i]);
    }

    //bubbleSort(11, a);
     
    //selectSort(11, a);

    //insertSort(11, a);

    //quickSort(a,0,10);

    //shellSort(a, 11);

    //heapSort(a, 10); 

    //mergeSort(a,11);

    mergeSort1(a, 11);

    printf("\n the result is:\n");
    for (int i = 0; i < 11; i++) {
        printf("%d ", a[i]);
    }

    getchar();
}