排序 - 简书

排序

分析一个算法从以下几个方面入手

最好情况、最坏情况、平均情况时间复杂度
时间复杂度的系数、常数、低阶。
比较次数和交换(移动次数);
- 基于比较的排序算法的执行过程会涉及两种操作过程，一种是元素比较大小。另一种是元素交换或移动。
- 排序算法的内存消耗原地排序特质空间复杂度是O(1)的排序算法。
- 稳定性如果待排序的序列中存在值相等的元素，经过排序之后，相等的元素之间原有的先后顺序不变。
- 两个相同的数字前后顺序没有改变，我们就把这种排序叫做稳定的排序算法。如果前后顺序变化了，那对应的排序算法就叫做不稳定的排序算法。
通过“有序度”和“逆序度”分析复杂度
- 有序度是数组中具有有序关系的元素对的个数。
- 满有序度：有序度就是n*(n-1)/2，
- 逆序度 = 满有序度 - 有序度
- 排序的过程就是增加有序度，减少逆序度的过程最后达到满有序度。

冒泡排序

1.冒泡排序只会操作相邻的两个数据，每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系，如果不满足
就让他俩交换。一次冒泡会让至少一个元素移动到它应该在的位置。重复n次就完成了n个数据的排序工作

void bubbleSort(int arr[],int n)
{
    if (n<=1) {
        return;
    }
    for (int i=0; i<n; i++) {
        bool flag = false;//提前退出冒泡排序的标志位
        for (int j=0; j<n-i-1; j++) {
            if (arr[j]>arr[j+1]) {
                //交换
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
                flag = true;
            }
        }
        if (!flag) {
            break;
        }
    }
}

2.插入排序

1.首先将数组中的数据分为两个区间 已排区间和未排区间
  初始已排区间只有一个元素就是数组的第一个元素。插入算法的核心思想就是取未排序区间中的元素，在已排序区间中找到合适的
  插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空。算法结束。
  2.两种操作
         一种是元素的比较 一种是元素的移动
  3.移动操作次数总是固定的 等于逆序度

    void insertSort(int arr[],int n)
    {
       if(n<=1) return;
        for(int i=1;i<n;i++)
        {
        int value = arr[i];//制作一个副本
        int j = i-1;//插入的位置
        for (;j>=0; j--) {
            if (arr[j]>value) {
                arr[j+1] = arr[j];
            }else
            {
                break;
            }
        }
        arr[j+1] = value;
    }
    
}

1.选择排序

 选择排序算法分为已排区间和未排区间,但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排区间的末尾。
 选择排序算法空间复杂度为O(1)，是一种原地排序算法，选择排序最好的时间复杂度、最坏和平均都是O(n2)
 选择排序是一种不稳定的排序算法。(稍差)

void selectSort(int arr[], int n)
{
    if (n<=1) {
        return;
    }
    for (int i=0; i<n; i++) {
        //1.确定一个最小的下标
        int minIndex = i;
        for (int j=i+1; j<n; j++) {
            if (arr[j]<arr[minIndex]) {
                minIndex = j;
            }
        }
        //交换
        int tmp;
        tmp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = tmp;
    }
}



    int main(int argc, const char * argv[]) {
    @autoreleasepool {
        int a[10]={ 8,3,2,1,6,5,4,7,10,9 };
        bubbleSort(a, 10);
        for(int i=0;i<10;i++)
        {
            printf("%d ",a[i]);
        }
    }
    return 0;
    }

最后编辑于：2018.12.25 10:43:09