YouTube视频插入排序-https://www.youtube.com/watch?v=JU767SDMDvA
这是我在C 中的实现
void insertionSort(void *data, uint32_t length, int8_t compareTo(const void * const, const
void * const), const size_t bytes){
uint32_t i;
for(i = 0; i < length; i++){
uint8_t isSorted;
int32_t j;
isSorted = 0;
for(j = i - 1; j > -1 && !isSorted; j--){
isSorted = 1;
if(compareTo((int8_t *)data + j * bytes, (int8_t *)data + (j + 1) * bytes) > 0){
uint32_t byteIndex;
void *valCopy;
valCopy = malloc(bytes);
memcpy(valCopy, (int8_t *)data + j * bytes, bytes);
for(byteIndex = 0; byteIndex < bytes; byteIndex++){
*((int8_t *)data + (j * bytes + byteIndex)) = *((int8_t *)data + ((j + 1) * bytes + byteIndex));
*((int8_t *)data + ((j + 1) * bytes + byteIndex)) = *((int8_t *)valCopy + byteIndex);
}
/**
instead of the for loop you can replace it with this to make it look more clean
memcpy((int8_t *)data + j * bytes, (int8_t *)data + (j + 1) * bytes, bytes);
memcpy((int8_t *)data + (j + 1) * bytes, valCopy, bytes);
**/
free(valCopy);
isSorted = 0;
}
}
}
}
int8_t compareTo(const void * const val1, const void * const val2){
if(*(const int32_t * const)val1 > *(const int32_t * const)val2)return 1;
else if(*(const int32_t * const)val1 < *(const int32_t * const)val2)return -1;
return 0;
}
int main(void){
int32_t i;
int32_t data[] = {2, 6, 5, 3, 8, 7, 1, 0};
int32_t dataLength = sizeof(data) / sizeof(*data);
insertionSort(data, dataLength, &compareTo, sizeof(int32_t));
for(i = 0; i < dataLength; i++){
printf("%d ", data[i]);
}
return 0;
}
我想知道是否有比每次使用memcpy或for循环复制值更有效的方法？
正如另一个答案所观察到的，不需要为每次交换调用malloc()和free()。所有这些额外的电话似乎确实是效率低下的最大根源。您最多需要一个malloc和一个free调用，但对于不超过您选择的限制的物品尺寸，您可以不使用任何。例如，
#define SMALL_ITEM_LIMIT 1024 /* for example */
// ...
void insertionSort(void *data, uint32_t length,
int8_t compareTo(const void * const, const void * const), const size_t bytes) {
char auto_buffer[SMALL_ITEM_LIMIT];
char *temp;
if (bytes > SMALL_ITEM_LIMIT) {
temp = malloc(bytes);
if (temp == NULL) {
// ... handle allocation failure ...
}
} else {
temp = auto_buffer;
}
// ... main part of the sort ...
if (temp != auto_buffer) {
free(temp);
}
}
作为次要事项，变量isSorted的使用是不必要的，并且有点笨拙。当当前元素到达其插入位置时，您可以通过从j循环中简单地break来避免它，并可能减少几个循环。
你问：
我想知道是否有比复制值更有效的方法每次使用memcpy或for循环？
对于这样的通用排序，如果您不知道要排序的项的类型，那么对于移动元素，除了大容量内存操作之外，别无选择。我倾向于从memcpy()和/或memmove()开始，因为它更清楚。在没有对各种情况进行测试以确定它是否真的提供了任何改进的情况下，不要使用内部循环。
但是，您不一定需要一次将元素移动一个位置。相反，在每次外循环迭代中，您可以在不移动任何东西的情况下定位插入位置，然后通过单个n-元素旋转执行插入。对于随机数据，这将倾向于执行更少的读取和写入。这种变化可能看起来是这样的(一些名称已经更改，以使其更清晰(：
void insertionSort(void *data, uint32_t item_count,
int compare(const void *, const void *), size_t item_size) {
char auto_buffer[SMALL_ITEM_LIMIT];
char *temp = (item_size > SMALL_ITEM_LIMIT) ? malloc(item_size) : auto_buffer;
if (temp) {
char *char_data = data; // for clarity; avoids having to cast all the time
for (uint32_t i = 1; i < count; i++) { // no point in starting at 0
// Find the insertion position
for (uint32_t j = i; j > 0; j--) {
if (compare(char_data + j * item_size,
char_data + (j - 1) * item_size) >= 0) {
break;
}
}
// Rotate the current item into position
if (j != i) {
memcpy(temp, char_data + i * item_size, item_size);
memmove(char_data + j * item_size,
char_data + (j + 1) * item_size,
(i - j) * item_size);
memcpy(char_data + j * item_size, temp, item_size);
}
}
if (temp != auto_buffer) {
free(temp);
}
} // else memory allocation failed
}
或者，在实践中，将旋转与比较更并行地实现，以更好地利用缓存和数据局部性，可能会更有效率。这就像每次交换只进行一半(或三分之一(的交换。它的排序循环是这样的：
for (uint32_t i = 1; i < count; i++) { // no point in starting at 0
// store element i
memcpy(temp, char_data + i * item_size, item_size);
// Find the insertion position
for (uint32_t j = i; j > 0; j--) {
if (compare(char_data + j * item_size,
char_data + (j - 1) * item_size) < 0) {
// shift element j - 1 up one position
memcpy(char_data + (j - 1) * item_size,
char_data + j * item_size,
item_size);
} else {
break;
}
}
if (j != i) {
// Put the erstwhile value of element i into its position
memcpy(char_data + j * item_size, temp, item_size);
}
}
在任何特定情况下，哪一个在实践中表现更好，这是一个需要通过测试来回答的问题。
实现中效率最高的部分是对malloc()和free()的不必要调用，它们只需要调用一次，然后在算法中的每个交换中重复使用。这是一个可能的实现：
void isort(void* ptr, size_t count, size_t size, int (*comp)(const void*, const void*))
{
size_t i;
size_t j;
bool sorted;
void* a;
void* b;
void* t;
// don't allocate temporary memory when unneeded
if (count == 0) return;
t = malloc(size);
for (i = 0; i < count; ++i)
{
sorted = false;
for (j = i - 1; j >= 0 && !sorted; --j)
{
sorted = true;
a = (char*)ptr + size * j;
b = (char*)ptr + size * (j + 1);
if (comp(a, b) > 0)
{
memcpy(t, a, size);
memcpy(a, b, size);
memcpy(b, t, size);
sorted = false;
}
}
}
free(t);
}
在godbolt 上试用
插入排序不适合在数组上使用，因为必须执行代价高昂的数组重新排列。应在linkedLists上使用插入排序。在数组上，一个类似但更好的算法是选择排序。当然，像快速排序或合并排序这样的分治算法也很好。