排序

排序

#include<iostream>
using namespace std;

//bubble sort 冒泡排序就是把小的元素往前调或者把大的元素往后调。冒泡排序是两个相邻的数进行比较，把大的放在后面
void bubbleSort(int a[], int n){
    int i, j,temp;
    for (i = 0; i < n-1; i++){
        //因为没经历一次i 排序后，最大的都会放在了最后，那么已经排序的就不用再比较了，经历i次就已经排好i个数，而减一就是7个数，两两比较就只比较了6次
        for (j = 0; j < n - 1 - i; j++){
            if (a[j]>a[j + 1]){
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
}

// Select sort 选择排序,在每次排序选择最小的出来，
void SelectSort(int a[], int n){
    int i, j,index,temp,min;
    for ( i = 0; i < n; i++){
        min = a[i];
        index = i;
        // 我把每一次排序的最小元素找出来，把下标标记一下，等这一次排序全部比较过直接把下标index的值跟下标为i的值交换
        for (j = i + 1; j < n; j++){
            // 一开始min的值是a[i],当找到比a[i]的值更小的时候，把min设为当前的a[j]值,然后跟剩余的值进行比较，找到最小的值并用index标记起来
            if (a[j]<min){
                min = a[j];
                index = j;
            }
        }
        // 这里只是为了判断一下上面那个循环又没做，没有做就代表当前a[i]已经是最小的了
        if (index != i){
            temp = a[i];
            a[i] = a[index];
            a[index] = temp;
        }
    }
}

// 插入排序
void insertSort(int a[], int n){
    int i,index,currentValue;
    for (i = 1; i < n; i++){
        if (a[i] < a[i - 1]){
            currentValue = a[i];
            index = i - 1;
            //如果当前元素小于上一个元素，那么元素后移
            while (currentValue < a[index])
            {
                a[index + 1] = a[index];
                index--;
                
            }
            // 把值插入到正确的位置
            a[index+1] = currentValue;
        }
    }
}

// 快速排序
void quickSort(int a[], int low, int high){

    if (low >= high)
    {
        return;
    }
    int first = low;
    int last = high;
    int key = a[first];/*用字表的第一个记录作为枢轴*/

    while (first < last)
    {
        while (first < last && a[last] >= key)
        {
            --last;
        }

        a[first] = a[last];/*将比第一个小的移到低端*/

        while (first < last && a[first] <= key)
        {
            ++first;
        }

        a[last] = a[first];
        /*将比第一个大的移到高端*/
    }
    a[first] = key;/*枢轴记录到位*/
    quickSort(a, low, first - 1);
    quickSort(a, first + 1, high);


}


int main(){
    //int data[] = { 2,44,38,5,47,15,36,26,27,3,46,4,4,19,50,48 };
    int data[] = { 6,2,7,3,8,9 };
    int i, j,length,temp;
    length = sizeof(data) / sizeof(int);
    //insertSort(data, length);
    quickSort(data, 0, length-1);

    for (i = 0; i < length; i++){
        cout << data[i] << " ";
    }

}

上面写了四个排序，分别是冒泡排序，选择排序，快速排序和插入排序，
以及一些个人笔记，以便忘了的时候重新记起，当然还有几个排序，归并，堆，二分。