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

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

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

算法：
对一个大小为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)

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

序号	插入式排序	选择式排序
1	在预排序的数组中插入数值，对数组中的数值集进行排序。	从列表中找出最小/最大的数字，并按升序/降序排序。
2	插入式排序是一种稳定的排序算法。	选择式排序是一种不稳定的排序算法。
3	当数组已经处于升序时，最佳情况下的时间复杂度为Ω(N)。在最坏情况和平均情况下有Θ(N2)。	对于最佳情况，最差情况和平均选择排序的复杂度为Θ(N2)。
4	插入式排序算法中进行的比较操作的数量少于所进行的交换操作。	选择式排序算法中进行的比较操作的数量多于进行的交换。
5	插入式排序比选择排序更有效。	选择式排序比插入排序的效率低。
6	插入式排序的元素是事先知道的，寻找正确的位置来放置它们。	放置元素的位置是事先知道的，在该位置上搜索要插入的元素。

易百教程

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

推荐

最受关注

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

推荐

最受关注

微信关注