」アルゴリズム:ソートアルゴリズム選択ソートと挿入ソート


🚀 What I Will Learn

  • 選択ソートの原理
  • を理解する
  • 挿入並べ替えの原理
  • を理解する.
    コンピュータ科学と数学では、ソートアルゴリズムは、番号順や辞書順などの要素を一定の順に並べたアルゴリズムです.

    ソートアルゴリズム


    19615;選択ソートは何ですか?


    1)最も基本的なソートアルゴリズム
    2)最小で前方に送信するソート方法を選択する
    3)最小のものをN回選択し、前にN回送信し、O(n²)の時間複雑度を持つ
    時間の複雑さ:問題を解決するのに必要な時間と入力された関数の関係.コンピュータ科学では,アルゴリズムの時間複雑度は入力された文字列長を表す関数であり,ワークアルゴリズムを用いて時間を定量化することを意味する.
  • ソート前
  • ソート後

  • 2朕選択順位の実施


    1)アレイ宣言
    #define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <limits.h>
    #define SIZE 1000
    
    int a[SIZE];
    int swap(int *a, int *b) { 
      int temp = *a;
      *a = *b;
      *b = temp;
    }
    2)選択ソートの実行
    int main(void) {
      int n, min, index;
      scanf("%d", &n);
      for (int i = 0; i < n; i++) scanf("%d", &a[i]); 
      for (int i = 0; i < n; i++) {
        min = INT_MAX;
        for (int j = i; j < n; j++) {
          if (min > a[j]) {
            min = a[j];
            index = j;
          } 
        }
        swap(&a[i], &a[index]); 
      }
      system("pause");
      return 0; 
    }

    3▼▼挿入順は何ですか?


    1)各数値の並べ替え方法を適切な位置に挿入する
    2)進入位置N回、選択回数N回、時間複雑度O(n²)3)一般的にソート動作より速い
  • ソート前
  • ソート中
  • は、2番目の要素4から、4に入る空間
  • を決定する.
  • 以降の3は、2と4の位置を決定するときに2と4の間の
  • に入る.
  • ソート後

  • 4朕挿入ソートの実現


    1)アレイ宣言
    #define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #define SIZE 1000
    
    int a[SIZE];
    int swap(int *a, int *b) {
      int temp = *a;
      *a = *b;
      *b = temp;
    }
    2)挿入ソートの実行
    int main(void) {
      int n;
      scanf("%d", &n);
      for (int i = 0; i < n; i++) scanf("%d", &a[i]); 
      for (int i = 0; i < n - 1; i++) {
          int j = i;
          while (j >= 0 && a[j] > a[j + 1]) {
            swap(&a[j], &a[j + 1]);
      	j--; 
          }
      } 
      system("pause"); 
      return 0;
    }

    ✨ tl;dr

  • 選択並べ替えおよび挿入並べ替えは、時間的複雑度O(n²)の最も単純な形式の並べ替えアルゴリズム
  • である.