几种常见的排序

spring

1.选择排序

• 比较后，符合条件每次都进行交换。

for (int i= 0;i<cnt-1;i++){
        for (int j=i + 1;j<cnt;j++){
            if(array[i]<array[j]){
                int tmp=array[i];
                array[i]=array[j];
                array[j]=tmp;
            }
        }
    }

2.冒泡排序

/* 冒泡排序 */
    for (int i = 0; i < cnt - 1; i ++) {
        for (int j = 0; j < cnt - i - 1; j ++) {
            if (array[j] < array[j + 1]) {
                int tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;
            }
        }
    }

3.插空排序

• 代码解析见注释。

        int  a[5]={9,8,10,2,20};
        int key,j;// key为每次被拿出的值（也就是初始提供“空”的值），j为要比较到的最大索引
        for (int i=1; i<5; i++) {// 直接插入排序
            key=a[i];// 取出当前要比较项
            for (j=i-1; j>=0&&a[j]>key; j--) {// 和直到索引j位置的元素逐一比较
                a[j+1]=a[j];// j为更新出来的新空（但是只要进了循环，此次循环结束就会进行一次j--操作，所以下面要+1）
            }
            a[j+1]=key;// j+1为最后留给key的空
        }

整体测试代码

#import <Foundation/Foundation.h>
void initArray(int array[],int cnt);
void selectSortForArray(int array[],int cnt);
void showArray(int array[],int cnt);


void initArray(int array[],int cnt)
{
    for(int i= 0;i<cnt;i++)
        array[i] = arc4random()  % 100;
}
void selectSortForArray(int array[],int cnt)
{
    /*for (int i = 0; i<cnt-1; i++){
        for (int j = i+1; j<cnt; j++)
        {if (array[i] < array[j]) {
                int tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
     }}}*/
    //****************这样每次比较后都交换元素位置**********
    for (int i= 0;i<cnt-1;i++){
        for (int j=i + 1;j<cnt;j++){
            if(array[i]<array[j]){
                int tmp=array[i];
                array[i]=array[j];
                array[j]=tmp;
            }
        }
//    }
//*****************这样每次比较只记住索引，内循环遍历一次完成后再交换（减少交换次数），*********
    for (int i = 0; i < cnt - 1; i++) {
        int tmp = 0;
        for (int j = i + 1; j < cnt; j++) {
            if (array[i] < array[j]) {
                tmp = j;
            }
            int c = array[i];
            array[i] = array[tmp];
            array[tmp] = c;
        }
    }
    /* 冒泡排序 */
    for (int i = 0; i < cnt - 1; i ++) {
        for (int j = 0; j < cnt - i - 1; j ++) {
            if (array[j] < array[j + 1]) {
                int tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;
            }
        }
    }
}
void showArray(int array[],int cnt)
{
    for (int i = 0; i<cnt; i++) {
        printf("%d ",array[i]);
    }
    printf("\n");
}

int main(int argc, const char * argv[])
{

    @autoreleasepool {
        
        // insert code here...
//        NSLog(@"Hello, World!");
//
        int array[10] = {0};
        initArray(array, 10);
        showArray(array,10);
        selectSortForArray(array, 10);
        showArray(array,10);
        
        // C-实现 插空排序
        int  a[5]={9,8,10,2,20};
        int key,j;// key为每次被拿出的值（也就是初始提供“空”的值），j为要比较到的最大索引
        for (int i=1; i<5; i++) {// 直接插入排序
            key=a[i];// 取出当前要比较项
            for (j=i-1; j>=0&&a[j]>key; j--) {// 和直到索引j位置的元素逐一比较
                a[j+1]=a[j];// j为更新出来的新空（但是只要进了循环，此次循环结束就会进行一次j--操作，所以下面要+1）
            }
            a[j+1]=key;// j+1为最后留给key的空
        }
        for (int i=0; i<5; i++) {
//            NSLog(@"%i",a[i]);
        }
        // OC实现
//        NSMutableArray *array=[NSMutableArray arrayWithObjects:@9,@8,@10,@2,@20, nil];
//        id key;
//        NSInteger j;
//        for (NSInteger i=1; i<array.count; i++) {
//            key=[array objectAtIndex:i];//取到每一个待插入的数据,从a[1]开始查找
//            for (j=i-1; j>=0&&array[j]>key; j--) {
//                // 如果之前的数比key大,就将这个数向后移动一个位置,留出空来让key插入就像整牌一样
//
//                [array exchangeObjectAtIndex:j+1 withObjectAtIndex:j];//交换
//            }
//            [array replaceObjectAtIndex:j+1 withObject:key];
//        }
//        for (key in array) {
//            NSLog(@"%@",key);
//        }
        printf("\n");
    }
    return 0;
}