算法导论9.2以期待线性时间做选择

www.myexceptions.net  网友分享于：2015-02-11  浏览：0次

```#include <stdint.h>
#include <time.h>
#include <iostream>
#ifdef __linux
#include <stdio.h>
#include <stdlib.h>
#endif

void swap(int64_t* A, uint64_t i, uint64_t j)
{
int64_t tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}

int64_t partition(int64_t* A, int64_t p, int64_t r)
{
int64_t x = A[r];
int64_t i = p;
for (int64_t j = p; j < r; j++)
{
if (A[j] <= x)
{
swap(A, i, j);
i++;
}
}
swap(A, i, r);
return i;
}

int64_t RandomizedPartition(int64_t* A, int64_t p, int64_t r)
{
int64_t i = (rand() % (r - p)) + p;
swap(A, i, r);
return partition(A, p, r);
}

// RANDOMIZED-SELECT(A, p, r, i)
// if p == r
//     return A[p]
// q = RANDOMIZED-PARTITION(A, p, r)
// k = q - p + 1
// if i == k
// return A[q]
// else if i < k
//     return RANDOMIZED-SELECT(A, p, q - 1, i)
// else
//     return RANDOMIZED-SELECT(A, q + 1, r, i - k)

int64_t RandomizedSelect(int64_t* A, int64_t p, int64_t r, int64_t i)
{
if (p == r)
{
return A[p];
}
int64_t q = RandomizedPartition(A, p, r);
int64_t k = q - p + 1;
if (i == k)
{
return A[q];
}
else if (i < k)
{
return RandomizedSelect(A, p, q - 1, i);
}
else
{
return RandomizedSelect(A, q + 1, r, i - k);
}
}
int main()
{
int64_t array[] = { 2, 8, 7, 1, 3, 5, 6, 4 };

std::cout << RandomizedSelect(array, 0, 7, 3) << std::endl;
getchar();
return 0;
}
```
```BIN     = bin
FMCSA   = find_max_crossing_subarray
IAS     = IA_solution
IST     = insertion_sort_t
LMSA    = liner_time_max_subarray
MERGE   = merge
MERGE_T = merge_t
VMS     = violate_max_subarray
STRA    = 4.2_strassen
COUNT_SORT = 8.2_counting_sort
MINIMUMMAXIMUM = 9.1_MinimumMaximum
RS = 9.2_RandomizedSelect
RQ = 7.3_RandomizedQuicksort
QS = 7.1_quicksort

CFLAGS = -g -Wall

all : \${BIN}/\${COUNT_SORT} \${BIN}/\${RS} \${BIN}/\${QS} \${BIN}/\${FMCSA} \${BIN}/\${RQ} \${BIN}/\${IAS} \${BIN}/\${IST} \${BIN}/\${LMSA} \${BIN}/\${MERGE} \${BIN}/\${MERGE_T} \${BIN}/\${VMS} \${BIN}/\${STRA} \${BIN}/\${MINIMUMMAXIMUM}

\${BIN}/\${COUNT_SORT} : \${COUNT_SORT}/counting_sort.cpp
g++ \${COUNT_SORT}/counting_sort.cpp \${CFLAGS} -o \${BIN}/\${COUNT_SORT}

\${BIN}/\${FMCSA} : \${FMCSA}/main.cpp \${FMCSA}/max_sub_array.h
g++ \${FMCSA}/main.cpp \${CFLAGS} -o \${BIN}/\${FMCSA}

\${BIN}/\${IAS} : \${IAS}/insertion_sort.cpp \${IAS}/insertion_sort.h
g++ \${IAS}/insertion_sort.cpp \${CFLAGS} -o \${BIN}/\${IAS}

\${BIN}/\${IST} : \${IST}/\${IST}.cpp \${IST}/\${IST}.h
g++ \${IST}/\${IST}.cpp \${CFLAGS} -o \${BIN}/\${IST}

\${BIN}/\${LMSA} : \${LMSA}/Source.cpp
g++ \${LMSA}/Source.cpp \${CFLAGS} -o \${BIN}/\${LMSA}

\${BIN}/\${MERGE} : \${MERGE}/\${MERGE}.cpp  \${MERGE}/\${MERGE}.h
g++ -std=c++0x \${MERGE}/\${MERGE}.cpp \${CFLAGS} -o \${BIN}/\${MERGE}

\${BIN}/\${MERGE_T} : \${MERGE_T}/\${MERGE_T}.cpp  \${MERGE_T}/\${MERGE_T}.h
g++ -std=c++0x \${MERGE_T}/\${MERGE_T}.cpp \${CFLAGS} -o \${BIN}/\${MERGE_T}

\${BIN}/\${VMS} : \${VMS}/Source.cpp
g++ \${VMS}/Source.cpp \${CFLAGS} -o \${BIN}/\${VMS}

\${BIN}/\${STRA} : \${STRA}/strassen.cpp \${STRA}/strassen.h
g++ -std=c++0x \${STRA}/strassen.cpp \${CFLAGS} -o \${BIN}/\${STRA}

\${BIN}/\${MINIMUMMAXIMUM} : \${MINIMUMMAXIMUM}/\${MINIMUMMAXIMUM}.cpp
g++ \${MINIMUMMAXIMUM}/\${MINIMUMMAXIMUM}.cpp \${CFLAGS} -o \${BIN}/\${MINIMUMMAXIMUM}

\${BIN}/\${RS} : \${RS}/\${RS}.cpp
g++ \${RS}/\${RS}.cpp \${CFLAGS} -o \${BIN}/\${RS}

\${BIN}/\${RQ} : \${RQ}/\${RQ}.cpp
g++ \${RQ}/\${RQ}.cpp \${CFLAGS} -o \${BIN}/\${RQ}

\${BIN}/\${QS} : \${QS}/\${QS}.cpp \${QS}/\${QS}.h
g++ \${QS}/\${QS}.cpp \${CFLAGS} -o \${BIN}/\${QS}

clean:
rm \${BIN}/*
```