Skip to content

O(n2)

Selection Sort

core idea

① put the smallest number in the first place 'at every loop'
② the index is the standard

code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
void selectionSort(int arr[],int n) {
   for (int i = 0; i < n; ++i)
        {
            int min_index = i;
            for (int j = i + 1; j < n; ++j) //j is the later number of i at any time
            {
                if (arr[j] < arr[min_index])
                {
                    min_index = j;  //find the min index in the loop
                }
                //we already get the smallest number in this loop 'when i still at the place which have not move to the next place'
                swap(arr[min_index],arr[i]);    //
            }
        }
}

when using swap directly,must add "using namespace std;"

Insertion Sort

core idea

find the second number as a key(standard),
use key to compare with the former numbers
if less,the former number(closing) set back one place & key keeping compare with the former numbers until key bigger than the former number or get the limitation(out of the range)

code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
    void insertionSort(int arr[],int n) {
        for (int j = 1; j < n; ++j)
        {
            int key = arr[j];
            int i = j - 1;
            for (j;key < arr[i] && i >= -1;--i)
            {
                arr[i + 1] = arr[i];
            }
            arr[i + 1] = key;
        }
    }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
template<typename T>
void insertionSort(T arr[], int n){

    for( int i = 1 ; i < n ; i ++ ) {

        // 寻找元素arr[i]合适的插入位置
        // 写法1
//        for( int j = i ; j > 0 ; j-- )
//            if( arr[j] < arr[j-1] )
//                swap( arr[j] , arr[j-1] );
//            else
//                break;

        // 写法2
//        for( int j = i ; j > 0 && arr[j] < arr[j-1] ; j -- )
//            swap( arr[j] , arr[j-1] );

//arr[j] < arr[j-1]  这样的原因是因为交换之后去一位一位和前一个位比较
//arr[j-1] > e 这样没有去一位一位的交换，只是去赋值

        // 写法3
        T e = arr[i];//相当于我们将要比较的值复制出来了
        int j; // j保存元素e应该插入的位置【千万注意在顶层循环下先声明】
        for (j = i; j > 0 && arr[j-1] > e; j--)
            arr[j] = arr[j-1];
        arr[j] = e;
    }

    return;
}