插入式排序和选择式排序的区别

在这篇文章中，我们将学习插入排序和选择排序之间的区别。

插入排序是一种简单的排序算法，其工作方式类似于对手中的扑克牌进行排序。数组实际上被分成了已排序和未排序的部分。未排序部分的值被挑选出来，放在排序部分的正确位置上。

算法：
对一个大小为n的数组进行升序排序。

• 在数组上从arr[1]到arr[n]进行迭代。
• 将当前的元素(key)与它的前一个元素进行比较。
• 如果关键元素比它的前一个小，则与之前的元素比较。将较大的元素向上移动一个位置，为被交换的元素腾出空间。

以下是插入排序的程序代码：

// C++ program for the insertion sort
#include <bits/stdc++.h>
using namespace std;

// Function to sort an array using
// insertion sort
void insertionSort(int arr[], int n)
{
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        // Move elements of arr[0..i-1],
        // that are greater than key to
        // one position ahead of their
        // current position
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

// Function to print an array of size N
void printArray(int arr[], int n)
{
    int i;

    // Print the array
    for (i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// Driver Code
int main()
{
    int arr[] = { 12, 11, 13, 5, 6 };
    int N = sizeof(arr) / sizeof(arr[0]);

    // Function Call
    insertionSort(arr, N);
    printArray(arr, N);

    return 0;
}

Java实现代码：

// Java program for the above approach
import java.util.*;
class YiibaiDemo
{

// Function to sort an array using
// insertion sort
static void insertionSort(int arr[], int n)
{
    int i, key, j;
    for (i = 1; i < n; i++)
    {
        key = arr[i];
        j = i - 1;

        // Move elements of arr[0..i-1],
        // that are greater than key to
        // one position ahead of their
        // current position
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

// Function to print an array of size N
static void printArray(int arr[], int n)
{
    int i;

    // Print the array
    for (i = 0; i < n; i++) {
        System.out.print(arr[i] + " ");
    }
    System.out.println();
}

// Driver code
public static void main(String[] args)
{
    int arr[] = { 12, 11, 13, 5, 6 };
    int N = arr.length;

    // Function Call
    insertionSort(arr, N);
    printArray(arr, N);
}
}

C#实现代码：

// C# program for the above approach
using System;
class YiibaiDemo
{

    // Function to sort an array using
    // insertion sort
    static void insertionSort(int[] arr, int n)
    {
        int i, key, j;
        for (i = 1; i < n; i++)
        {
            key = arr[i];
            j = i - 1;

            // Move elements of arr[0..i-1],
            // that are greater than key to
            // one position ahead of their
            // current position
            while (j >= 0 && arr[j] > key)
            {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    // Function to print an array of size N
    static void printArray(int[] arr, int n)
    {
        int i;

        // Print the array
        for (i = 0; i < n; i++)
        {
            Console.Write(arr[i] + " ");
        }
        Console.WriteLine();
    }

    // Driver code
    static public void Main()
    {
        int[] arr = new int[] { 12, 11, 13, 5, 6 };
        int N = arr.Length;

        // Function Call
        insertionSort(arr, N);
        printArray(arr, N);
    }
}

Python实现代码：

# Python 3 program for the insertion sort

# Function to sort an array using
# insertion sort
def insertionSort(arr, n):
    i = 0
    key = 0
    j = 0
    for i in range(1,n,1):
        key = arr[i]
        j = i - 1

        # Move elements of arr[0..i-1],
        # that are greater than key to
        # one position ahead of their
        # current position
        while (j >= 0 and arr[j] > key):
            arr[j + 1] = arr[j]
            j = j - 1
        arr[j + 1] = key

# Function to print an array of size N
def printArray(arr, n):
    i = 0

    # Print the array
    for i in range(n):
        print(arr[i],end = " ")
    print("n",end = "")

# Driver Code
if __name__ == '__main__':
    arr = [12, 11, 13, 5, 6]
    N = len(arr)

    # Function Call
    insertionSort(arr, N)
    printArray(arr, N)

选择排序算法对一个数组进行排序的方法是从未排序的部分中反复找到最小的元素(考虑升序)，并将其放在开头。该算法在一个给定的数组中维护两个子数组。

• 子数组已经被排序了。
• 剩下的子数是未排序的。

在选择排序的每一次迭代中，从未排序的子阵列中挑选最小的元素(考虑升序)，并将其移到已排序的子阵列中。

下面是一个上述选择排序算法步骤的例子。

arr[] = 64 25 12 22 11

// Find the minimum element in arr[0...4]
// and place it at beginning
11 25 12 22 64

// Find the minimum element in arr[1...4]
// and place it at beginning of arr[1...4]
11 12 25 22 64

// Find the minimum element in arr[2...4]
// and place it at beginning of arr[2...4]
11 12 22 25 64

// Find the minimum element in arr[3...4]
// and place it at beginning of arr[3...4]
11 12 22 25 64

// C++ program for implementation of
// selection sort
#include <bits/stdc++.h>
using namespace std;

// Function to swap two number
void swap(int* xp, int* yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

// Function to implement the selection
// sort
void selectionSort(int arr[], int n)
{
    int i, j, min_idx;

    // One by one move boundary of
    // unsorted subarray
    for (i = 0; i < n - 1; i++) {

        // Find the minimum element
        // in unsorted array
        min_idx = i;
        for (j = i + 1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;

        // Swap the found minimum element
        // with the first element
        swap(&arr[min_idx], &arr[i]);
    }
}

// Function to print an array
void printArray(int arr[], int size)
{
    int i;

    for (i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// Driver Code
int main()
{
    int arr[] = { 64, 25, 12, 22, 11 };
    int n = sizeof(arr) / sizeof(arr[0]);

    // Function Call
    selectionSort(arr, n);
    cout << "Sorted array: n";

    // Print the array
    printArray(arr, n);
    return 0;
}
// C++ program for implementation of
// selection sort
#include <bits/stdc++.h>
using namespace std;

// Function to swap two number
void swap(int* xp, int* yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

// Function to implement the selection
// sort
void selectionSort(int arr[], int n)
{
    int i, j, min_idx;

    // One by one move boundary of
    // unsorted subarray
    for (i = 0; i < n - 1; i++) {

        // Find the minimum element
        // in unsorted array
        min_idx = i;
        for (j = i + 1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;

        // Swap the found minimum element
        // with the first element
        swap(&arr[min_idx], &arr[i]);
    }
}

// Function to print an array
void printArray(int arr[], int size)
{
    int i;

    for (i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// Driver Code
int main()
{
    int arr[] = { 64, 25, 12, 22, 11 };
    int n = sizeof(arr) / sizeof(arr[0]);

    // Function Call
    selectionSort(arr, n);
    cout << "Sorted array: n";

    // Print the array
    printArray(arr, n);
    return 0;
}

选择排序的Java实现代码：

// Java program for implementation of
// selection sort
import java.util.*;
class YiibaiDemo
{

// Function to implement the selection
// sort
static void selectionSort(int arr[], int n)
{
    int i, j, min_idx;

    // One by one move boundary of
    // unsorted subarray
    for (i = 0; i < n - 1; i++)
    {

        // Find the minimum element
        // in unsorted array
        min_idx = i;
        for (j = i + 1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;

        // Swap the found minimum element
        // with the first element
        int temp = arr[min_idx];
        arr[min_idx]= arr[i];
        arr[i] = temp;
    }
}

// Function to print an array
static void printArray(int arr[], int size)
{
    int i;

    for (i = 0; i < size; i++) {
        System.out.print(arr[i]+ " ");
    }
    System.out.println();
}

// Driver Code
public static void main(String[] args)
{
    int arr[] = { 64, 25, 12, 22, 11 };
    int n = arr.length;

    // Function Call
    selectionSort(arr, n);
    System.out.print("Sorted array: n");

    // Print the array
    printArray(arr, n);
}
}

选择排序的Python实现代码：

# Python3 program for implementation of
# selection sort

# Function to implement the selection
# sort
def selectionSort(arr, n):

    # One by one move boundary of
    # unsorted subarray
    for i in range(n - 1):

        # Find the minimum element
        # in unsorted array
        min_idx = i
        for j in range(i + 1, n):
            if (arr[j] < arr[min_idx]):
                min_idx = j

        # Swap the found minimum element
        # with the first element
        arr[min_idx], arr[i] = arr[i], arr[min_idx]

# Function to print an array
def printArray(arr, size):

    for i in range(size):
        print(arr[i], end = " ")

    print()

# Driver Code
if __name__ == "__main__":

    arr = [64, 25, 12, 22, 11]
    n = len(arr)

    # Function Call
    selectionSort(arr, n)
    print("Sorted array: ")

    # Print the array
    printArray(arr, n)

插入式排序和选择式排序的表格区别。