经典的选择排序 C++版O(n^2)

这么简单的算法之前写过思路,这次是复习一遍。
如果看思路:https://www.z88j.com/106.html (这个是php版本的 不过算法和语言没多大关系)
值得注意的是 c++ swap 实际性能并没有 普通的变量交换性能高。好像是因为泛型 要进行类型判断。
c++选择排序代码:

#include <iostream>

using namespace std;
/**
 * 选择排序 
 * @param arr
 * @param n
 */
void selectionSort(int arr[],int n){
    for (int i = 0; i < n; ++i) {
        //寻找[i,n]区间里的最小值
        int minIndex = i;
        for (int j = i+1; j < n; ++j) {
            if (arr[j] < arr[minIndex])
                minIndex = j;
            swap(arr[i],arr[minIndex]);
        }
    }
};
int main() {
    std::cout << "Hello, World!" << std::endl;
    int a[10] = {10,9,8,7,6,5,4,3,2,1};
    selectionSort(a,10);
    for (int i = 0; i < 10; ++i) {
        cout << a[i] <<" ";
        cout << endl;
    }
    return 0;
}

使用swap交换变量

template<typename T>
void bubbleSort2(T arr[], int n){
    int newn; //使用newn进行优化

    do{
        newn = 0;
        for(int i = 1; i < n; i ++){
            if(arr[i-1] > arr[i]){
                swap(arr[i-1], arr[i]);
                // 记录最后一次的交换位置,在此之后的元素在下一轮扫描中均不考虑
                newn = i;            
            }        
        }
        n = newn;
    }while(newn > 0);
}

使用基本交换

template<typename T>
void bubbleSort4(T arr[], int n){
    int newn; //使用newn进行优化
    int i,j;
    T temp;
    do{
        newn = 0;
        for(i = 1; i < n; i ++){
            if(arr[i-1] > arr[i]){
                temp = arr[i-1];
                arr[i-1] = arr[i];
                arr[i] = temp;
                // 记录最后一次的交换位置,在此之后的元素在下一轮扫描中均不考虑
                newn = i;            
            }        
        }
        n = newn;
    }while(newn > 0);
}

经典的选择排序 C++版O(n^2)

原创文章,作者:星辰,如若转载,请注明出处:https://www.z88j.com/290.html

(15)
打赏 微信扫一扫 微信扫一扫
上一篇 2021年6月8日 下午3:33
下一篇 2021年6月16日 上午11:20

相关推荐

  • 顺序查找算法【工作见解】

    星辰工作中遇到要查找数组数据取出 工作场景:有两个数组一个是 [[“时间”,”今天时间数据”],[“时间”,”今天时间数据”],…] 另一个是 [[“时间”,”昨天时间数据”]…

    php 2020年12月11日
    91000
  • 两个数组的交集 解法

    给定两个数组,编写一个函数来计算它们的交集。   示例 1: 输入:nums1 = [1,2,2,1], nums2 = [2,2] 输出:[2] 示例 2: 输入:nums1 =…

    快速排序 2021年6月8日
    45800
  • 选择排序【工作见解】

    工作中遇到排序需求,不能数据库排,我就代码排序了。 $startTime = microtime(true); $len = count($list); for ($i=0;$i&…

    快速排序 2020年12月10日
    1.0K10
  • 203. 移除链表元素php解法

    给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。(力扣的题 编号203哈) 示例 1: …

    php 2021年6月17日
    83700
  • 877. 石子游戏php解法

    亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行,每堆都有正整数颗石子 piles[i] 。 游戏以谁手中的石子最多来决出胜负。石子的总数是奇数,所以没有平局。 亚历克斯和李轮流…

    算法 2021年6月16日
    48500
  • php链表中倒数第k个节点 解法

    刷力扣算法日常 题目: 输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。例如,一个链表有6个节点,从头节点开始,…

    php 2020年12月2日
    80100

发表回复

登录后才能评论