C++选择排序算法实例详解

本文实例为大家分享了C++选择排序算法的具体代码,供大家参考,具体内容如下

基本思想

每一趟从无序区中选出最小的元素,顺序放在有序区的最后,直到全部元素排序完毕。
由于选择排序每一趟总是从无序区中选出全局最小(或最大)的元素,所以适用于从大量元速度中选择一部分排序元素。例如,从10000个元素中选出最小的前10位元素。

直接选择排序

1.排序思路

从第i趟开始,从当前无序区arr[i…n-1]中选出最小元素arr[k],将它与有序区的最后一个元素,也就是无序区的第一个元素交换。每趟排序后,有序区增加一个元素,无序区减少一个元素,且有序区中所有元素均小于等于无序区中的元素。经过n-1趟排序后,无序区只剩下arr[n-1]一个元素,它必然为整个序列的最大值,故无需再排。

2.排序算法

void SelectSort(int *arr, int size)
{
  if (arr == NULL)
    return;

  //1.找到无序区中最小的元素和它的下标
  int i, j;
  for (i = 0; i < size - 1; i++)
  {
    int k = i;
    for (j = i + 1; j < size; j++)
    {
      if (arr[j] < arr[k])
      {
        k = j;
      }

    }
    //2.把最小的元素与无序区第一个元素交换
    //swap(arr[i], arr[k]);
    if (k != i)
    {
      int tmp = arr[i];
      arr[i] = arr[k];
      arr[k] = tmp;
    }
  }
}

3.算法分析

由于要选出最小值,故无序区中的每个元素都要参与比较,所以无论初始数据序列的状态如何,总的比较次数为:

C = n-1 +n-2+n-3+…+2+1 = n(n-1)/2

故直接选择排序的时间复杂度为O(N^2),空间复杂度为O(1)。直接选择排序是一个不稳定的算法。例如,排序序列为{5,3,2,5,4,1},第一趟排序后得到{1,3,4,5,4,5},两个5的相对位置发生了变化。

4.优化版本

每趟排序同时找出最大值和最小值,把最小值放在序列的左边,最大值放在序列的右边,然后同时缩小左右排序范围。

//优化,每趟排序同时找出最大值和最小值
void SelectSort1(int *arr, int size)
{
  if (arr == NULL)
    return;

  int left = 0;
  int right = size - 1;
  while (left < right)
  {
    for (int i = left; i < right; i++)
    {
      if (arr[i] < arr[left])
        swap(arr[i], arr[left]);
      if (arr[i] > arr[right])
        swap(arr[i], arr[right]);
    }
    left++;
    right--;
  }
}

堆排序

1.排序思路

堆排序是一种树形选择排序方法,在排序过程中,将arr[0…n-1]看成一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲节点和孩子结点之间的内在关系,在当前无序区中选择最大(或最小)的元素。
下标从0开始,节点i的两个孩子节点可表示为2*i+1、2*i+2。

2.排序算法

void AdjustDown(int *arr, int size, int parent)
{
  int child = 2 * parent + 1;

  while (child < size)
  {
    if (child + 1 < size && arr[child] < arr[child + 1])
    {
      child++;
    }

    if (arr[parent] < arr[child])
    {
      swap(arr[parent], arr[child]);
      parent = child;
      child = 2 * parent + 1;
    }
    else
      break;
  }
}

void HeapSort(int *arr, int size)
{
  if (arr == NULL)
    return;

  //1.建立初始堆(此处为大堆)
  int root;
  for (root = (size / 2)-1; root >= 0; root--)
  {
    AdjustDown(arr, size, root);
  }

  //2.将arr[0]与arr[n-1]交换,然后再调整arr[0...n-1],使其满足大堆,如此反复操作
  for (root = size-1; root >= 1; root--)
  {
    swap(arr[root], arr[0]);
    AdjustDown(arr, root, 0);
  }
}

3.算法分析

堆排序的时间主要由建堆和反复调整堆这两部分的时间构成,由于可以把堆看成完全二叉树的结构,所以堆排序的时间复杂度为O(N*lgN),空间复杂度为O(1),堆排序算法不稳定。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • C++插入排序算法实例详解

    本文实例为大家分享了C++插入排序算法实例的具体代码,供大家参考,具体内容如下 基本思想 每次将一个待排序的元素,按其大小插入到已经排好序的子序列的适当位置,知道全部元素插入完成为止. 直接插入排序 1.排序思路 arr[0...i-1]为有序区(刚开始时i=1,有序区只有arr[0]一个元素),arr[i...size]为待排序区,每次将待排序区的第一个元素arr[i]插入到有序区中的适当位置,每趟操作都使有序区增加一个元素,待排序区减少一个元素. 2.排序算法 void InsertSort

  • C++小知识:用++i替代i++

    静态代码分析工具可简化编码过程,检测出错误并帮助修复.PVS-Studio 是一个用于 C/C++ 的静态代码分析工具.该团队检测了 200 多个 C/C++ 开源项目,包括了 Unreal Engine.Php.Haiku.Qt 和 Linux 内核等知名项目.于是他们每天分享一个错误案例,并给出相应建议. 这个 bug 是在 Unreal Engine 4 的源代码中发现的. 错误代码: void FSlateNotificationManager::GetWindows( TArray<

  • C++实现洗牌发牌排序功能的示例代码

    在内存中模拟出一副牌,然后模拟洗牌,发牌等动作. 流程是这样的:构建一副牌保存到一个数组中-洗牌-创建玩家-向玩家发牌–输出每个玩家的牌. #include <stdio.h> #include <stdlib.h> #include <time.h> //定义扑克的花色 enum Suit{ heart, spade, diamond, club, joker1, joker2 }; //一副牌的数量 #define CARD_COUNT 54 //定义扑克 type

  • 剑指offer之C++语言实现链表(两种删除节点方式)

    1 问题 用C++语言实现链表 2 代码实现 #include <iostream> #include <stdlib.h> using namespace std; class List { public: List(); ~List(); List* createNode(int value);//创建节点 bool insertNode(List *node);//插入节点 void printList();//打印节点 bool deleteNode(List *node)

  • C++二维数组中数组元素存储地址的计算疑问讲解

    关于二维数组中数组元素的存储地址,有同学问出了个好问题. 在我的课件中,出现了下面的讲解: a[i][j]的地址是p+(i*col+j)*d(d是数组元素所占的字节数). 同学编程序进行验证,出问题了: 地球停止转动了也必须先赞这种学习方式! 同学问:"老师,第一张图的4,我怎么觉得不对呢?第二张图我没4,结果好像也对,这里面差在哪呢?" 我的答复:"两个都对." 第一张图在讲原理,是我们在人脑里面要以"字节"为单位计算,p为首地址,单位是字节,

  • Python使用ctypes调用C/C++的方法

    python使用ctypes调用C/C++ 1. ctpes介绍 ctypes is a foreign function library for Python. It provides C compatible data types, and allows calling functions in DLLs or shared libraries. It can be used to wrap these libraries in pure Python. 官方文档地址: https://do

  • C++实践排序函数模板项目的参考方法

    [项目-排序函数模板] 已知 void Sort(int a[],int size); void Sort(double a[],int size); 是一个函数模板的两个实例,其功能是将数组a中的前size个元素按从小到大顺序排列.试设计这个函数模板. 参考解答: #include<iostream> using namespace std; template<class T> void Sort(T set[],int n) { int i,j; T temp; for(i=1

  • Android Java调用自己C++类库的实例讲解

    Android Java 如何调用自己的 C++ 的类库 下面以 Java 调用 C++ 的加法运算函数为例,做简单说明. (使用 Android Studio 3 编译) 首先编译 c++ 类库 创建独立目录存放 c++ 文件,例如 "app/src/main/cpp/add.cpp",内容如下 #include <jni.h> extern "C" JNIEXPORT jint JNICALL Java_com_example_liyi_demo_U

  • C++小知识:不要去做编译器的工作

    对于C++编程的老鸟来说,有时候他们喜欢把一些东西按照编译器的工作原理进行改写,以便提高代码的运行效率.这么做确实高明,也能体现出程序员的水平,但是这么做也是有风险的.因为有时候你可能会因为一些简单的笔误,而造成非常难以察觉的错误.本文就给出了类似的例子. 这个Bug 出现在MySQL源代码中. 错误代码: static int rr_cmp(uchar *a,uchar *b) { if (a[0] != b[0]) return (int) a[0] - (int) b[0]; if (a[

  • C++小知识:用合适的工具来分析你的代码

    静态代码分析工具可简化编码过程,检测出错误并帮助修复.有个国外团队检测了 200 多个 C/C++ 开源项目,包括了 Php.Qt 和 Linux 内核等知名项目.于是他们每天分享一个错误案例,并给出相应建议.今天的案例来自 LibreOffice 项目. 错误代码 BOOL WINAPI DllMain( HINSTANCE hinstDLL, DWORD fdwReason, LPVOID lpvReserved ) { .... CreateThread( NULL, 0, ParentM

随机推荐