本文實(shí)例為大家分享了C++選擇排序算法的具體代碼，供大家參考，具體內(nèi)容如下

基本思想

每一趟從無(wú)序區(qū)中選出最小的元素，順序放在有序區(qū)的最后，直到全部元素排序完畢。
由于選擇排序每一趟總是從無(wú)序區(qū)中選出全局最?。ɑ蜃畲螅┑脑兀赃m用于從大量元速度中選擇一部分排序元素。例如，從10000個(gè)元素中選出最小的前10位元素。

直接選擇排序

1.排序思路

從第i趟開(kāi)始，從當(dāng)前無(wú)序區(qū)arr[i…n-1]中選出最小元素arr[k]，將它與有序區(qū)的最后一個(gè)元素，也就是無(wú)序區(qū)的第一個(gè)元素交換。每趟排序后，有序區(qū)增加一個(gè)元素，無(wú)序區(qū)減少一個(gè)元素，且有序區(qū)中所有元素均小于等于無(wú)序區(qū)中的元素。經(jīng)過(guò)n-1趟排序后，無(wú)序區(qū)只剩下arr[n-1]一個(gè)元素，它必然為整個(gè)序列的最大值，故無(wú)需再排。

2.排序算法

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

 //1.找到無(wú)序區(qū)中最小的元素和它的下標(biāo)
 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.把最小的元素與無(wú)序區(qū)第一個(gè)元素交換
  //swap(arr[i], arr[k]);
  if (k != i)
  {
   int tmp = arr[i];
   arr[i] = arr[k];
   arr[k] = tmp;
  }
 }
}

3.算法分析

由于要選出最小值，故無(wú)序區(qū)中的每個(gè)元素都要參與比較，所以無(wú)論初始數(shù)據(jù)序列的狀態(tài)如何，總的比較次數(shù)為：

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

故直接選擇排序的時(shí)間復(fù)雜度為O(N^2)，空間復(fù)雜度為O(1)。直接選擇排序是一個(gè)不穩(wěn)定的算法。例如，排序序列為{5，3，2，5，4，1}，第一趟排序后得到{1，3，4，5，4，5}，兩個(gè)5的相對(duì)位置發(fā)生了變化。

4.優(yōu)化版本

每趟排序同時(shí)找出最大值和最小值，把最小值放在序列的左邊，最大值放在序列的右邊，然后同時(shí)縮小左右排序范圍。

//優(yōu)化，每趟排序同時(shí)找出最大值和最小值
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.排序思路

堆排序是一種樹(shù)形選擇排序方法，在排序過(guò)程中，將arr[0…n-1]看成一棵完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹(shù)中雙親節(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系，在當(dāng)前無(wú)序區(qū)中選擇最大（或最?。┑脑?。
下標(biāo)從0開(kāi)始，節(jié)點(diǎn)i的兩個(gè)孩子節(jié)點(diǎn)可表示為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]交換，然后再調(diào)整arr[0...n-1]，使其滿(mǎn)足大堆，如此反復(fù)操作
 for (root = size-1; root >= 1; root--)
 {
  swap(arr[root], arr[0]);
  AdjustDown(arr, root, 0);
 }
}

3.算法分析

堆排序的時(shí)間主要由建堆和反復(fù)調(diào)整堆這兩部分的時(shí)間構(gòu)成，由于可以把堆看成完全二叉樹(shù)的結(jié)構(gòu)，所以堆排序的時(shí)間復(fù)雜度為O(N*lgN)，空間復(fù)雜度為O(1)，堆排序算法不穩(wěn)定。

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評(píng)論