选择排序 | C++

Question

你好，我是 C++ 的新手，我写了一个选择排序程序，你能帮我说一下为什么我们在 swap 函数中放置星号 (*)，而在 selectionSort 中我们应该在 <> 我的意思是我们不能说：

int newint = a;
  a = b;
  b = newint;

而不是：

int newint = *a;
  *a = *b;
  *b = newint;

主要代码：

using namespace std;
void swap(int *a, int *b);
void selectionSort(int arr[], int size);
void printArray(int arr[], int size);

int main() {
    int arr[] = {20, 12, 10, 15, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, size);
    cout << "Sorted array in Acsending Order:\n";
    printArray(arr, size);
}
// ================================================
// swap function to swap two element of the array
void swap(int *a, int *b){
  int newint = *a;
  *a = *b;
  *b = newint;
}
// ================================================
// the selection function made of two main loop
void selectionSort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        int min = i;
        for (int j = i + 1; j < size; j++) {
            if (arr[j] < arr[min])
                min = j;
            }
        swap(&arr[min], &arr[i]);
        }
    }
// ================================================
// print function to show the final result
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

Answer 1

a和b是pointers，作为参数接收，传递它们的地址。它们就像手指。例如，你用手指指向一个值，我用手指指向另一个值。当您打算交换我们指向的内容时，您需要指向我之前指向的位置，我也需要指向您之前指向的位置。你的建议是交换我们的手指。

或者，更技术地说：您需要交换指针指向的值，而不是切换指针的内存位置。

另一个类比可能是地址。你住在某个地址，我住在另一个地址。如果我们交换地址，那么你搬进我以前的地址，我搬进你以前的地址。但是我们并没有实际将我们住的房子搬到我们的新地址。

Answer 2

指针是通过引用传递的，也就是说，如果你在一个函数中改变它，它也会在函数调用后改变。喜欢：

int a=5;
setTo6(&a);//Implementation: *a=6
//a=6

另一方面，所有其他不是指针的参数都是按值传递的。这意味着，如果您在函数中更改它们，它不会在调用方更改。

int a=5;
setTo6ByValue(a);//Implementation: a=6
//a=5

所以，考虑这两个交换函数： (1)

void swap(int *a, int *b){
  int newint = *a;
  *a = *b;
  *b = newint;
}

和 (2)

void swap(int a, int b){
  int newint = a;
  a = b;
  b = newint;
}

第一个会发生什么？

int a=5;//Address=0x1000
int b=6;//Address=0x1004
swap(&a,&b);

将指针传递给函数，然后将地址0x1000(指向a的指针)的内容存入newint.

*a = *b;

将地址 0x1000 处的 int 设置为地址 b (0x1004) 处的值。

*b = newint;

将地址 0x1004 处的 int 设置为 newint 的值。

第二个会做什么？

int a=5;//Maybe in the r8 register
int b=6;//r9 register
swap(a,b);

我们将有以下汇编代码（真正未优化）：

mov , %r8 //int a = 5
mov , %r9 //int b = 6
//Setup registers (
mov %r8, %rdi
mov %r9, %rsi
call swap // swap(a,b)
....



swap:
     mov %rdi, %rax //int newint=a
     mov %rsi, %rdi //a=b
     mov %rax, %rsi //b=newint
     ret //Return to caller

它们不会被改变，因为你只改变了变量。

这两个概念被称为按值调用和按引用调用。这里进一步说明： https://www.guru99.com/call-by-value-vs-call-by-reference.html

选择排序 | C++

Selection Sort | c++

c++

algorithm

c++14

selection-sort