数据结构：选择排序

1.冒泡排序

这个使接触c语言最基础的算法

稳定性：稳定

时复杂度O(N^2)

2.直接选择排序

直接选择排序是针对冒泡排序的优化，因为他一次可以选出作用域中的最大值和最小值；并将作用域缩小；

时间复杂度：小于O(N^2)；仅仅是小一点而已

稳定性：不稳定；有些情况控制不住，选数时是稳定的，但是交换的时候可能会控制不住

int main() 
{int a[10] = { 9,8,7,6,5,4,3,2,1,0 };
int n = sizeof(a) / sizeof(int);
int begin = 0, end = n - 1;
while (begin < end){
int maxi = begin, mini = begin;
for (int i = begin; i <= end; i++){
if (a[i] > a[maxi]){
maxi = i;
}
if (a[i] < a[mini]){
mini = i;
}
}
swap(a[begin], a[mini]);
if (begin == maxi){
maxi = mini;
}
swap(a[end], a[maxi]);
begin++;
end--;
}
for (auto x : a) {
cout << x << endl;
}
return 0;
}

if (begin == maxi){            //精华都在这条语句上；
            maxi = mini;
        }

//a[begin]=9(最大值)，a[mini]=2,a[max]=9;
//此程序是根据下标来交换数值的；begin==max时，swap(a[begin], a[mini])交换后
//a[begin]=2，a[mini]=9,a[max]=2;因为是根据下标来确定数值；

//所以a[end]与a[max]交换后，把数值2换出去了；

3.堆排序

主要解决topk问题；优先级队列问题

时间复杂度：O(N^logN)

大堆：顶上那个最大（树中任何一个父亲都大于等于孩子）

小堆：顶上那个最小（树中任何一个父亲都小于等于孩子）

数据结构的构建，完全是建立在C语言上的；而在C++上是可以直接使用容器来进行操作；这里就不再写代码实现

具体的想理解，只能通过做题：力扣：1046、703、692、295；

原文地址：https://blog.csdn.net/qincjun/article/details/142845225

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！