也是面试题

一、插入排序

1.插入排序—直接插入排序(Straight Insertion Sort)

思路

遍历整个数组，如果遇到a[i]<a[i -1], 把a[i] 和a[i -1]~a[0]进行比较，比a[i]大就往后移，直到a[i]比它前面的要小，把a[i] 插入到该处。

代码

void insertSort(int array[] , int leng )
{
    for (int i = 1; i < leng; i ++) {
        
        if (array[i] < array[i - 1]) {  //如果第i个元素比他前面的元素小，就要往前面查
            
            int j = i - 1;// 第i个前面一个元素
            
            int x = (int)array[i]; //取出要插入的第i个元素
            
            while (x < (int)array[j]) {  //如果第i个小于第i-1
                
                array[j + 1] = array[j]; //数组往后移动一位
                
                j --;
            }
            array[j+1] = x;// 把第i个插入到相应的位置
            for (int i = 0; i < leng; i ++) {
                
                printf("%d,",array[i]);
            }
            printf("\n");
        }
    }
    printf("结果\n");
    for (int i = 0; i < leng; i ++) {
        
        printf("%d,",array[i]);
        
    }
    
}

效率

稳定的排序方法，时间复杂度O(n^2)

二、选择排序

1.选择排序—简单选择排序（Simple Selection Sort）

思路

1.找出a[0]~a[n]中最小的放在a[0]；
2.找出a[1]~a[n]中最小的放在a[1];
3.找出a[2]~a[n]中最小的放在a[2];
...直到最后排完。

代码

int selectMinKey(int a[],int n,int i) //从第i个搜索到第n个 找出最小的index
{
    int k = i;
    for (int j = i + 1; j < n; j ++) {
        
        if (a[k]>a[j]) {
            
            k = j;//替换值小的index
        }
    }
    
    return k;
    
}

void selectSort(int a[] , int n)
{
    int key, tmp;
    for(int i = 0; i< n; ++i) {
        key = selectMinKey(a, n,i);           //选择最小的元素
        if(key != i){ //如果找出的最小的index 不是i 的话，就把小的换过去
            tmp = a[i];
            a[i] = a[key];
            a[key] = tmp;
        }
        
        for (int i = 0; i < n; i ++) {
            
            printf("%d,",a[i]);
        }
        printf("\n");
    }
}

效率

稳定的排序方法，时间复杂度O(n^2)

三、交换排序

1.交换排序—冒泡排序（Bubble Sort）

思路

比较a[0]~a[n] ,交换比a[i]小的数，让大的数往下沉，小的往上冒

代码

void bubbleSort(int a[], int n){
    for(int i =0 ; i< n-1; ++i) {
        for(int j = 0; j < n-i-1; ++j) {//通过这个交换，最大的会沉到最底下
            if(a[j] > a[j+1])
            {
                int tmp = a[j] ;
                a[j] = a[j+1] ;
                a[j+1] = tmp;
            }
        }
        
        for (int i = 0; i < n; i ++) {
            
            printf("%d,",a[i]);
        }
        printf("\n");
    }
}

效率

稳定的排序方法，时间复杂度O(n^2)