삽입 정렬 기반 표 정렬

구체 적 인 지식 포 인 트 는 중국 대학 MOOC 에 가서 절 대 판 데이터 구 조 를 보 세 요. 여 기 는 알고리즘 의 실현 만 제시 합 니 다.

#include
using namespace std;

/*
       ：
                               。       sizeof()   ， 
                sizeof()   ，            ，            。

      ：
                         ，       arr[pos[0]], arr[pos[1]] ... 

        ：
                      ，                         

                      、      
*/

int* tableSort(int *arr, int len)
{
    int *pos = new int[len];
    for(int i = 0; i < len; i++)
        pos[i] = i;
    for(int i = 1; i < len; i++)
    {
        int temp = arr[i], j, tp = pos[i];
        for(j = i - 1; j >= 0 && arr[pos[j]] > temp; j--)
            pos[j + 1] = pos[j];
        pos[j + 1] = tp;
    }
    return pos;
}

void tableSortCastToPhysicalSort(int *arr, int *pos, int len)
{
    for(int i = 0; i < len; i++)
    {
        if(pos[i] != i)
        {
            int temp = arr[i];          
            int j = i, k = i;           
            while(pos[k] != j)          
            {
                arr[k] = arr[pos[k]];
                int t = pos[k];
                pos[k] = k;
                k = t;
            }
            arr[k] = temp;
            pos[k] = k;
        }
    }
} 
int main()
{
    int arr[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
//  int arr[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
//  int arr[10] = {8, 1, 4, 9, 0, 3, 5, 2, 7, 6};
    int *pos = tableSort(arr, 10);
    for(int i = 0; i < 10; i++)
        cout << arr[pos[i]] << " ";
    cout << endl;
    tableSortCastToPhysicalSort(arr, pos, 10);
    for(int i = 0; i < 10; i++)
        cout << arr[i] << " ";
    return 0;
}