随笔 - 25, 文章 - 0, 评论 - 6, 引用 - 0
数据加载中……

七种排序算法的简单分析与实现

#pragma once

/**//*
                    --- 冒泡排序 --- 
自下而上的两两比较,小泡排在大泡前,一趟冒出一个最小泡。
*/


void BubbleSort(int nArray[], int nLength)
{
    
int i = nLength - 1;
    
int j = 0;
    
int temp = 0;

    
for (int i = nLength - 1; i > 0--i)
    
{
        
for (int j = nLength - 2; j >= nLength - i - 1 ; --j)
        
{
            
if (nArray[j] > nArray[j + 1])
            
{
                temp 
= nArray[j + 1];
                nArray[j 
+ 1= nArray[j];
                nArray[j] 
= temp;
            }

        }

    }

}



/**//*
                    --- 选择排序 --- 
自下而上的两两比较,记录最小数的下标,将最上面的数与最小数交换。
*/


void SelectSort(int nArray[], int nLength)
{
    
int tempIndex = 0;
    
int tempValue = 0;

    
for (int i = 0; i < nLength; ++i)
    
{
        tempIndex 
= i;
        
for (int j = i + 1; j < nLength; ++j)
        
{
            
if (nArray[tempIndex] > nArray[j])
            
{
                tempIndex 
= j;
            }

        }

        tempValue 
= nArray[i];
        nArray[i] 
= nArray[tempIndex];
        nArray[tempIndex] 
= tempValue;
    }

}



/**//*
                    --- 插入排序 --- 
将数据插入到已排序的序列中,边找合适的位置,边移动数据,找到合适位置插入数据。
*/


void InsertSort(int nArray[], int nLength)
{
    
for (int i = 1; i < nLength; ++i)
    
{
        
int temp = nArray[i];
        
int j = i;
        
for (; j > 0 && nArray[j - 1> temp; --j)
        
{
            nArray[j] 
= nArray[j - 1];
        }

        nArray[j] 
= temp;
    }
    
}



/**//*
                    --- 快速排序 --- 
是对冒泡排序的改进。
1.先从数列中取出一个数作为基准数;
2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边;
3.再对左右区间重复第二步,直到各区间只有一个数.

分区过程可以形象的描述为“挖坑填数”:
1.将基准数nBase挖出形成第一个坑nArray[nLow];
2.nHigh--由后向前找比nBase小的数,找到后挖出此数填前一个坑nArray[nLow]中;
3.nLow++由前向后找比nBase大的数,找到后也挖出此数填到前一个坑nArray[nHigh]中;
4.再重复执行2,3二步,直到nLow==nHigh,将基准数nBase填入nArray[nLow]中.
*/


int AdjustArray(int nArray[], int nLow, int nHigh)
{
    
int nBase = nArray[nLow];

    
while(nLow < nHigh)
    
{
        
while(nLow < nHigh && nBase <= nArray[nHigh])
            
--nHigh;
        
if (nLow < nHigh)
        
{
            nArray[nLow
++= nArray[nHigh];
        }


        
while(nLow < nHigh && nBase > nArray[nLow])
            
++nLow;
        
if (nLow < nHigh)
        
{    
            nArray[nHigh
--= nArray[nLow];
        }

    }

    nArray[nLow] 
= nBase;
    
return nLow;
}


void QuickSort(int nArray[], int nLow, int nHigh)
{
    
if (nLow < nHigh)
    
{
        
int nMid = AdjustArray(nArray, nLow, nHigh);
        QuickSort(nArray, 
0, nMid - 1);
        QuickSort(nArray, nMid 
+ 1, nHigh);
    }

}



/**//*                
                    --- 希尔排序 --- 
是对直接插入排序算法的改进,又称缩小增量排序。
1、将数组进行分组,下标相差d的为一组;
2、对每组中全部元素进行排序;
3、然后再用一个较小的增量d, 重复1、2,直到d为1时,排序完成。

一般增量取值为上一次的一半,d = 1/2 d,第一次取值为数组长度的一半。
*/


void ShellSort(int nArray[], int nLength)
{
    
for (int nDifference = nLength / 2; nDifference > 0; nDifference = nDifference / 2)
    
{
        
for (int i = nDifference; i < nLength; ++i)
        
{
            
int temp = nArray[i];
            
int j = i;
            
for (; j > 0 && nArray[j - 1> temp; --j)
            
{
                nArray[j] 
= nArray[j - 1];
            }

            nArray[j] 
= temp;
        }

    }

}



/**//*                
                    --- 归并排序 --- 
是将两个已经排序的序列合并成一个有序序列。
1、待排序序列分为两个子序列;
2、每个子序列重复步骤1,直到每个子序列只有一个元素;
3、按大小顺序合并两个子序列;
4、重复步骤3,直到合并为一个整体有序序列,排序完成。
*/


void Merge(int nArray[], int nLow, int nHigh)
{
    
int nFirst = nLow;
    
int nMid = (nLow + nHigh) / 2;
    
int nSecond = nMid + 1;
    
int* p = (int*)malloc(sizeof(int* (nHigh - nLow + 1));
    
int nIndex = 0;

    
while(nFirst <= nMid && nSecond <= nHigh)
    
{
        
if (nArray[nFirst] > nArray[nSecond])
        
{
            p[nIndex] 
= nArray[nSecond++];
        }

        
else
        
{
            p[nIndex] 
= nArray[nFirst++];
        }

        
++nIndex;
    }


    
while (nFirst <= nMid)
    
{    
        p[nIndex
++= nArray[nFirst++];
    }


    
while (nSecond <= nHigh)
    
{    
        p[nIndex
++= nArray[nSecond++];
    }


    
for (int i = 0; i <= nIndex && nLow <= nHigh;)
    
{
        nArray[nLow
++= p[i++];
    }

    free(p);
}


void MergeSort(int nArray[], int nLow, int nHigh)
{
    
if (nLow < nHigh)
    
{
        
int nMid = (nLow + nHigh) / 2;
        MergeSort(nArray, nLow, nMid);
        MergeSort(nArray, nMid
+1, nHigh);
        Merge(nArray, nLow, nHigh);
    }

}



/**//*            
                    --- 堆排序 --- 
1、先将数组转换为完全二叉树;
2、调整二叉树形如大顶堆;
3、将根结点与最后一个叶子结点互换,即将最大元素放在数组的末尾,数组的长度减一;
4、再重复2、3,直到数组长度为1,排序完成。
*/


void AdjustHeap(int nArray[], int nLength, int nIndex)
{
    
int nLeft = nIndex * 2 + 1;
    
int nRight = nIndex * 2 + 2;
    
int nParent = nIndex;

    
while(nLeft < nLength && nRight < nLength)
    
{
        
int nBigIndex = (nArray[nLeft] > nArray[nRight] ? nLeft : nRight);
        
if (nArray[nParent] < nArray[nBigIndex])
        
{
            
int temp = nArray[nParent];
            nArray[nParent] 
= nArray[nBigIndex];
            nArray[nBigIndex] 
= temp;

            nLeft 
= nBigIndex * 2 + 1;
            nRight 
= nBigIndex * 2 + 2;
        }

        
break;
    }

}


void BuildHeap(int nArray[], int nLength)
{
    
for (int i = nLength / 2 - 1; i >= 0--i)
    
{
        AdjustHeap(nArray, nLength, i);
    }

}


void HeapSort(int nArray[], int nLength)
{
    BuildHeap(nArray, nLength);

    
while(nLength > 1)
    
{
        
int temp = nArray[0];
        nArray[
0= nArray[nLength - 1];
        nArray[nLength 
- 1= temp;
        AdjustHeap(nArray, 
--nLength, 0);
    }

}


void Test_Sort()
{
    
int nArray[5= {1,3,2,5,4};
    
//BubbleSort(nArray, 5);
    
//SelectSort(nArray, 5);
    
//InsertSort(nArray, 5);
    
//QuickSort(nArray, 0, 4);
    
//ShellSort(nArray, 5);
    
//MergeSort(nArray, 0, 4);
    HeapSort(nArray, 5);
    
for (int n = 0; n < 5++n)
    
{
        std::cout 
<< nArray[n] << " ";
    }

    std::cout 
<< std::endl;
}

posted on 2013-03-25 21:01 chenjt3533 阅读(2476) 评论(4)  编辑 收藏 引用 所属分类: C/C++

评论

# re: 七种排序算法的简单分析与实现  回复  更多评论   

学习了
2013-03-26 14:05 | 溪流

# re: 七种排序算法的简单分析与实现  回复  更多评论   

这个必须收藏起来
2013-03-28 09:20 | 岁月漫步

# re: 七种排序算法的简单分析与实现[未登录]  回复  更多评论   

冒泡排序不正确

int a[] = {2,1,8,7,4,3,6,5};
BubbleSort(a, 8);

12347856
2013-04-04 08:26 | 路人甲

# re: 七种排序算法的简单分析与实现  回复  更多评论   

@路人甲

谢谢指出,已做修改
2013-04-04 09:36 | chenjt3533

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理