C++插入排序

Question

我有一个名为 WordSort(worddata W [], int count) 的函数，它被输入两个变量 1 - worddata 是保存文件中给定单词信息的数组。 count 只是计数器变量，用于查看我们正在查看数组中的哪个单词。

读入该程序的words.txt 文件只是一串单词。

this is a list of words
there are letters and numbers
23 people recommend this program.

功能如下：

void WordSort (worddata W [], int count)
{
  for (int i=1; i < count; i++)
         {
           for (int j=i; j > 0 && W[j-1].word > W[j].word; j--)
             {
               Swap(W[j], W[j-1]);
             }
         }
}

交换函数假设只要 j > 0 或列表结束，就将每个元素与其前面的元素交换。我对如何完成交换功能感到困惑，这是给我的示例。

void Swap (worddata & a, worddata & b)
{
 int += a;
 a = b;
 b =+;
}

Swap 应该将每个元素与其前面的元素交换

我认为WordSort功能工作正常，唯一缺少的是Swap功能。有人能给我指出正确的方向或者更好地向我解释插入排序吗？

Answer 1

void insertion_sort()
{


    /* Algorithm : Insertion Sort
     * Coded by .
    */
    int num;
    /*
     * Asking the User no of Integers he/she wants to enter
     */
    cout << "Enter no of integers u want to enter: ";
    cin >> num;
    /* Creating an Array to store the integers*/
    int s[num];
    /*Taking Integers from the User */
    for(int i = 0 ; i < num ; i++)
    {
        cout << "Integer " << i+1 << " is : ";
        int x;
        cin >> x;
        s[i] = x;
    }
    /* The Magic of INSERTION SORT */
    for(int j = 1 ; j <= (num-1) ; j++)
    {
        int key = s[j]; 
        int k = j-1;

        while(k >=0 && key <= s[k])
        {
            s[k+1] = s[k];
            k = k - 1;
        }
        s[k+1]=key;

    }
    /*Printing Out the Sorted List */
    cout << "The Sorted List is \n\n";
    for(int i = 0 ; i < num ; i++)
    {
        cout << s[i] << "  ";
    }

}

Answer 2

使用标准库 std::swap 代替。在你的循环中：

for (...)
{
    std:swap(W[j], W[j-1]);
}

std::swap 要求 worddata 类具有显式或隐式定义的复制构造函数和赋值运算符。

Answer 3

交换应该看起来像这样——我不知道你的例子是如何接近的。

void Swap (worddata & a, worddata & b)
{
 worddata temp = a;
 a = b;
 b = temp;
}

Answer 4

使用“for 循环”进行插入排序（2 次迭代）

#include<iostream>
using namespace std;


int insertion(int arr[], int size_arr)
{
    int i,j,n, temp;

    for(i=1;i<size_arr; i++){
            j=i-1;
            temp = arr[i];
            for (j; j >=  0; j--)
        {
            if(arr[j] > temp){
                        arr[j+1] = arr[j];
                        arr[j] = temp;
            }
        }
            arr[j] = temp;
      }

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

int main(){
    int arr[] = {3,38,1,44,66,23,105,90,4,6};
    int size_arr = sizeof(arr) / sizeof(arr[0]);
    insertion(arr,size_arr);
    return 0;
}

Answer 5

#include <iostream>


void printArr(int arr[], int size)
{
    for(int i=0; i<size; i++)
        std::cout << arr[i] << " "; 

    std::cout<<std::endl;
}

void insertionSort(int arr[],int size){
    for (int i=1; i<size; i++){
        int temp=arr[i];
        int prev=i-1;
        while( prev>=0 && arr[prev]>temp )
        {
            arr[prev+1]=arr[prev];
            arr[prev]=temp;
            prev = prev-1;
        }
    }
}

int main()
{
    int arr[]={5,4,8,2,1};
    insertionSort(arr,5);
    printArr(arr,5);
}