最新消息:Rockyxia Web技术博客全新改版,响应式布局满足各种设备各种尺寸的访问需求。

以空间换时间的简单排序

后台开发语言 prgcao 1252浏览

sort.dist.cpp

/**
* filename:sort_dist.cpp
* env: Linux localhost.localdomain 2.6.18-164.el5 #1
* SMP Tue Aug 18 15:51:54 EDT 2009 i686 i686 i386 GNU/Linux
* author:caogl
**/
#include <stdio.h>
#include <string.h>
/**
* 取最值下标
* input:arr, length, isMax
* output:arr, index
* isMax:true=取最大值, false=取最小值
* return:errorCode
*/
unsigned int getExtremumIndex
(int * arr, unsigned int length, bool isMax, unsigned int* index)
{
    if (arr == NULL) {
        return -1;
    }

    (*index) = 0;
    unsigned int i;
    if (isMax) {
        for (i = 1; i < length; i++) {
            if (arr[*index] < arr[i]) {
                (*index) = i;
            }
        }
    } else {
        for (i = 1; i < length; i++) {
            if (arr[*index] > arr[i]) {
                (*index) = i;
            }
        }
    }

    return 0;
}

/**
* 测试getExtremumIndex
*/
void testGetExtremumIndex()
{
    int arr[] = {15, -89, 6, 0, -654, 695};
    unsigned int index = -1;
    unsigned int length = sizeof(arr)/sizeof(int);
    getExtremumIndex(arr, length, false, &index);
    printf("max=%d\n", arr[index]);
}


void disp(int * arr, unsigned int length)
{
    for (int i = 0; i < length; i++) {
        printf("%d\t", arr[i]);
    }
    printf("\n");
}

/**
* input:arr, arrLength
* output:arrSorted
*/
void sort(int * arr, unsigned int arrLength, int* arrSorted)
{
    unsigned int indexOfMax = -1;
    unsigned int indexOfMin = -1;

    getExtremumIndex(arr, arrLength, true, &indexOfMax);
    getExtremumIndex(arr, arrLength, false, &indexOfMin);

    //由于c中数组下标从0开始,而不能从负数开始,所以将使用0到_最值之差_
    //{称待排序的数值为n, 即arr中的元素
    //vector: 以n为下标, 以该n是否存在为值
    unsigned int vectorLength = arr[indexOfMax] - arr[indexOfMin] + 1;
    bool* vector = new bool[vectorLength];
    //}

    memset(vector, false, vectorLength);

    for (unsigned int i = 0; i <arrLength; i++) {
        vector[ arr[i] - arr[indexOfMin]] = true;
    }

    unsigned int j = 0;
    for (unsigned int i = 0; i <vectorLength; i++) {
        if (vector[i]) {
            arrSorted[j] = i + arr[indexOfMin];
            j++;
        }
    }

    delete[] vector;
}

void testSort()
{
    int arr[] = {15, -89, 6, 0, -654, 695};
    unsigned int arrLength = sizeof(arr)/sizeof(int);
    int* arrSorted = new int[arrLength];

    sort(arr, arrLength, arrSorted);

    disp(arr, arrLength);
    disp(arrSorted, arrLength);

    delete[] arrSorted;
}

int main()
{
    printf("dist\n");
    testSort();
}

/**
* run commond :
*	F=sort.dist;
*	g++ -c $F.cpp -o $F.obj; g++ $F.obj -o $F.app; ./$F.app
* output:
*	dist
*	15      -89     6       0       -654    695
*	-654    -89     0       6       15      695
**/

转载请注明:Rockyxia Web技术博客 » 以空间换时间的简单排序
感谢阅读,如果您发现文章中有表述不准确,欢迎提出来,也欢迎交流相关问题,你可以去这里进行一对一问答交流。

(本篇完)